## 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"],
]
```
word = `"ABCCED"`, -> returns `true`,
word = `"SEE"`, -> returns `true`,
word = `"ABCB"`, -> returns `false`.

 ``` 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 > &board, string word) { if(board.empty() || board[0].empty()) return false; vector> visited(board.size(), vector(board[0].size(),false)); for(int i=0; i> &board, vector> &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中的字符。

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

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

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

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

2. This comment has been removed by the author.

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.

2. what is its time complexity?

3. This comment has been removed by the author.

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

["ABCE"],
["SFCS"],