Problem description:

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.

1
2
3
4
5
6
7
8
9
10
11
12
Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution:

  1. Since the question mentioned there’s only one possible solution, we should use DFS.
  2. Use pre_check to see if any chac in word is not in board
  3. Temporary set board[i][j] to other character.
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False
        if not word:
            return True
        if not self.pre_check(board, word):
            return False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    if self.dfs(board, i, j, word):
                        return True
        return False
    
    def pre_check(self, board, word):
        letters = set()
        for i in range(len(board)):
            for j in range(len(board[0])):
                letters.add(board[i][j])
        for letter in word:
            if letter not in letters:
                return False
        return True
    
    def dfs(self, board, i, j, word):
        if len(word) == 0:
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
            return False
        # check other directions
        tmp = board[i][j]
        board[i][j] = '#'
        
        if self.dfs(board, i-1, j, word[1:]):
            return True
        if self.dfs(board, i+1, j, word[1:]):
            return True
        if self.dfs(board, i, j-1, word[1:]):
            return True
        if self.dfs(board, i, j+1, word[1:]):
            return True
        board[i][j] = tmp
        return False
  1. use DFS to find whether the word exist
  2. create a 2D bool array to record used elements in each DFS, the range should be [rowNum][colNum]
  3. find word with start in each slot[i][j]

In auxiliary function:
First we check pos is equal to word.length(), return true if it’s the same.
Second, if anything is out of range, then return false.
Third, return false if (we already visited this slot) || ([i][j] is different from the word[pos])

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
28
29
30
31
32
33
34
35
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty() || !word.length()) return false; //nothing in board || nothing in word
        int rowNum= board.size(), colNum= board[0].size();
        vector<vector<bool>> visited(rowNum, vector<bool>(colNum, false)); //create a visit array to check if visited
        
        for(int i =0; i< rowNum; ++i){
            for(int j= 0; j< colNum; ++j){
                //use [i][j] as start point, search for word
                if(exist(board, visited, word, i, j, 0)) return true;
            }
        }
        return false;
    }
    
    bool exist(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int i, int j, int pos) {
        if(pos == word.length()) return true;
        if( i< 0 || j< 0 || i> board.size()-1 || j>board[0].size()-1) return false; //edge case for size
        if(visited[i][j] || board[i][j] != word.at(pos)) return false; 
        //already came this slot || [i][j] is different from word[pos]
        
        visited[i][j] = true;
        
        //DFS
        if (exist(board, visited, word, i - 1, j, pos + 1) //check toward left
            || exist(board, visited, word, i + 1, j, pos + 1) //check toward right
            || exist(board, visited, word, i, j - 1, pos + 1) //check toward top
            || exist(board, visited, word, i, j + 1, pos + 1)) //check toward bottom
            return true; 
        
        visited[i][j] = false; //this slot can not make a same search word
        return false;
    }
};

Reference:
https://goo.gl/QLs5yW