Tuesday, November 18, 2014

[LeetCode] Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

思路:

以board上的每个cell为出发点,利用depth first search向上下左右四个方向搜索匹配word。搜索的时候要考虑board的边界,cell是否已经在DFS的路径上被用过,以及cell上的值是否与word的当前字符匹配。为了跟踪DFS的路径避免同一个cell被访问多次,使用一个visited矩阵来代表board上任意的cell(i, j)是否已经被访问过。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if(board.empty() || board[0].empty()) return false;
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(),false));
        for(int i=0; i<board.size(); i++) {
            for(int j=0; j<board[i].size(); j++) {
                if(findWord(board, visited, i, j, word, 0)) return true;
            }
        }
        return false;
    }
    
    bool findWord(vector<vector<char>> &board, vector<vector<bool>> &visited, int row, int col, string &word, int index) {
        if(index==word.size()) return true;
        if(row<0 || col<0 || row>=board.size() || col>=board[0].size() || visited[row][col] || board[row][col]!=word[index]) 
            return false;
            
        visited[row][col] = true;
        if(findWord(board, visited, row-1, col, word, index+1)) return true;  
        if(findWord(board, visited, row+1, col, word, index+1)) return true;
        if(findWord(board, visited, row, col-1, word, index+1)) return true;
        if(findWord(board, visited, row, col+1, word, index+1)) return true;
        visited[row][col] = false;
        return false;
    }
};

总结:
ln 16是这题最关键的点,包括了3个判断:
(1) 当前坐标是否在board内
(2) 当前cell是否已经在本次DFS路径上已经被访问
(3) 当前cell是否匹配当前word中的字符。

13 comments:

  1. Replies
    1. can't agree more! He is SO good!

      Delete
    2. I always forget 剪枝 during backtracking ... such as line 25 in this example. Good to learn it once again! Thanks YanBing!

      Delete
  2. line 15 is not enough, should add condition of word[i][j] ==word.get(index)

    ReplyDelete
    Replies
    1. line 15 is enough because the line 16 will not continue the recursive call if board[row][col]!=word[index].

      Delete
    2. This comment has been removed by the author.

      Delete
    3. valid index range is [ 0 ... word.size()-1 ], therefore when index reaches word.size(), the whole word has been parsed ... which also means in last round of DFS, its line#16 did check letter at word.size()-1 index.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. visited should not be used as using it will not pass cases such as:

    ["ABCE"],
    ["SFCS"],
    ["ADEE"]
    word: ABCBA

    ReplyDelete
    Replies
    1. 3rd example given shows that any letter in grid can not be reused.

      Delete
  5. This comment has been removed by the author.

    ReplyDelete