leetcode BFS

本次题解包括：

• 126 Word Ladder II
• 127 Word Ladder
• 130 Surrounded Regions

127 Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

题目地址：leetcode Surrounded Regions

题意：给定起始和结束字符串，还有个字典，要求每次最多变化一个字母成字典里的单词，求最短的步数使得起始字符串变为结束字符串。

思路：BFS。一开始TLE了，看了DISCUSS人家是直接变换字符串！而我是比较每个单词是否差一个字母。

废话不多说。

• 将start入队列
• 每次取出队首（一共取当前层的长度），对队首每个字母分别进行变换（a~z)，判断其是否在字典中，如果存在，加入队列。
• 每一层结束后，将dis+1

改进版是用双向BFS，这样速度更快。

• 和单向的不同在于，如果取出队首进行变化，变化的某一个字符串t在另一个方向的bfs中(如从start开始遍历的，而end已经遍历过t）说明有start->end的路径，将步数和累加即可。

单向的BFS

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dic):
        if start==end: return 1
        n =len(start)
        atoz=map(chr,xrange(ord('a'),ord('z')+1))
        q , vis ,dis= [start],set(),2
        vis.add(start)
        while q:                  
            for i in xrange(len(q)):
                cur = q.pop(0)
                for j in xrange(n):
                    for k in atoz:
                        t=cur[:j]+k+cur[j+1:]
                        if t==end:return dis
                        if t in dic and t not in vis :
                            q.append(t)
                            vis.add(t)
            dis+=1          
        return 0

双向BFS

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dic):
        if start==end: return 1
        n =len(start)
        atoz=map(chr,xrange(ord('a'),ord('z')+1))
        q_start , vis_start ,dis_start= [start],set([start]),1
        q_end ,    vis_end,   dis_end = [end],set([end]),1
        while q_start and q_end:                  
            for i in xrange(len(q_start)):
                cur = q_start.pop(0)
                for j in xrange(n):
                    for k in atoz:
                        t=cur[:j]+k+cur[j+1:]
                        if t in vis_end:return dis_start+dis_end
                        if t in dic and t not in vis_start :
                            q_start.append(t)
                            vis_start.add(t)
            dis_start+=1  
            for i in xrange(len(q_end)):
                cur = q_end.pop(0)
                for j in xrange(n):
                    for k in atoz:
                        t=cur[:j]+k+cur[j+1:]
                        if t in vis_start:return dis_start+dis_end
                        if t in dic and t not in vis_end :
                            q_end.append(t)
                            vis_end.add(t)
            dis_end+=1   
        return 0

 

126 Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]

Return

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

传送门

题意：给定起始和结束字符串，还有个字典，要求每次最多变化一个字母成字典里的单词，，输出所有最短的步数使得起始字符串变为结束字符串的过程。

思路：请先做127题！

一开始是采用类似127的做法，不过每次入队列的是路径，每次取路径最后一个元素判断。结果TLE了。

后来参考别人做法，先BFS出路径，然后DFS。还是TLE了。

之后把图建出来，只要a和b相差一个字母，那么我们就建一条a->b 和b->a的边。

再进行BFS。

需要注意的是：

• 标记使用过的单词应该这一层都遍历过才能标记，否则会出现答案不全。

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def findLadders(self, start, end, dic):
        n =len(start)
        edge= {}
        dic.add(start)
        dic.add(end)
        for i in dic: edge[i]=[]
        for cur in dic:                  
            for j in xrange(n):
                for k in xrange(ord(cur[j])+1, 123):
                    to=cur[:j]+chr(k)+cur[j+1:]
                    if to in dic :
                        edge[to].append(cur)
                        edge[cur].append(to)
        
        q ,vis , ans =[[start]] ,set([start]) ,[]
        flag=False
        while not flag and q:
            allword=[]
            for _ in xrange(len(q)):
                curPath = q.pop(0)
                cur=curPath[-1]
                for i in edge[cur]:
                    if i==end:
                        ans.append(curPath+[end])
                        flag=True
                    if i not in vis:
                        q.append(curPath+[i])
                        allword.append(i)
            vis = set(allword)
        return ans

 

130 Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

题目地址：leetcode Surrounded Regions

题目大意：给定二维数组，如果一些O四周（上下左右）都是X，那么将O改为X。

思路：BFS。把O相邻的所有加入队列。如果有一个可以触碰到边界，那么说明没有全部为X，不用替换。

class Solution:
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        if not board: return
        m , n = len(board),len(board[0])
        vis =[[False for j in range(n)]for i in range(m)]
        dx,dy= [1,-1,0,0],[0,0,1,-1]

        for i in range(m):
            for j in range(n):
                if board[i][j]=='X' or vis[i][j]: continue
                q,q2=[],[]
                flag = True
                q.append((i,j))
                q2.append((i,j))
                while q:
                    curx ,cury=q.pop(0)
                    for k in range(4):
                        nx , ny = curx+dx[k],cury+dy[k]
                        if nx < 0 or ny <0 or nx >=m or ny>=n:
                            flag=False
                            continue
                        if vis[nx][ny] or board[nx][ny]=='X': continue
                        vis[nx][ny]= True
                        q.append((nx,ny))
                        q2.append((nx,ny))
                
                if flag:
                    for x,y in q2:
                        board[x][y]='X'

但其实有更简单的方法： 将边界上的点及其可达的O标记为‘A'，然后遍历board, 将A改为O, 将O改为X即可。

C++

const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

class Solution {
	void dfs(int i, int j, vector<vector<char>> &board) {
		board[i][j] = 'A';
		for (int k = 0; k < 4; ++k) {
			int nx = i + dx[k], ny = j + dy[k];
			if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size())
				continue;
			if (board[nx][ny] == 'O') {
				dfs(nx, ny, board);
			}
		}
	}

public:
	void solve(vector<vector<char>>& board) {
		if (board.empty()) return;
		for (int i = 0; i < board.size(); ++i) {
			if (board[i][0] == 'O')
				dfs(i, 0, board);
			if (board[i][board[0].size() - 1] == 'O')
				dfs(i, board[0].size() - 1, board);
		}
		for (int j = 0; j < board[0].size(); ++j) {
			if (board[0][j] == 'O')
				dfs(0, j, board);
			if (board[board.size() - 1][j] == 'O')
				dfs(board.size() - 1, j, board);
		}
		for (int i = 0; i < board.size(); ++i) {
			for (int j = 0; j < board[0].size(); ++j) {
				if (board[i][j] == 'A')
					board[i][j] = 'O';
				else if (board[i][j] == 'O')
					board[i][j] = 'X';
			}
		}
	}
};

Python

class Solution(object):
    def dfs(self, i, j, board):
        if board[i][j] != 'O': return
        board[i][j] = 'A'
        for nx, ny in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if nx < 0 or ny < 0 or nx >= len(board) or ny >= len(board[0]):
                continue
            self.dfs(nx, ny, board)
    
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]: return
        for i in range(len(board)):
            self.dfs(i, 0, board)
            self.dfs(i, len(board[0]) - 1, board)
        
        for j in range(len(board[0])):
            self.dfs(0, j, board)
            self.dfs(len(board) - 1, j, board)
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'