题目链接：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.
这道题的要求是在二维网格中查找单词。单词可以是网格中水平和垂直方向的相邻字母连接而成，且每个字母只可以使用至多1次。
查找单词是否在二维数组中出现，只需依次从数组中的每个字母作为要查找单词word的首字母开始搜索，在搜索的时候递归搜索上下左右的四个方向，同时搜索过的地方需要用符号标记下。
时间复杂度：O(???)
空间复杂度：O(1)
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)
{
for(int i = 0; i < board.size(); ++ i)
for(int j = 0; j < board[i].size(); ++ j)
if(exist(board, i, j, word, 0))
return true;
return false;
}
private:
bool exist(vector<vector<char> > &board, int x, int y, string word, int i)
{
if(board[x][y] == word[i])
{
if(i == word.size() - 1)
return true;
board[x][y] = '#';
if(x + 1 < board.size() && exist(board, x + 1, y, word, i + 1))
return true;
if(x - 1 >= 0 && exist(board, x - 1, y, word, i + 1))
return true;
if(y + 1 < board[0].size() && exist(board, x, y + 1, word, i + 1))
return true;
if(y - 1 >= 0 && exist(board, x, y - 1, word, i + 1))
return true;
board[x][y] = word[i];
}
return false;
}
};