题目链接：Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must 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 in a word.
For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Return [“eat”,”oath”].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
If the current candidate does not exist in all words’ prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.
这道题的要求是在单词列表中找出二维网格中出现的单词。单词可以是网格中水平和垂直方向的相邻字母连接而成，且每个字母只可以使用至多1次。提示中指出可以利用和之前的字典树Implement Trie (Prefix Tree)的思路。
这是Word Search的第二版。可以先利用前面的思路，对每个单词在board中进行深度优先搜索，如果找到，就记录下来。代码如下，不过问题就是超时。
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
46
47
48
class Solution
{
public:
vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
{
unordered_set<string> uss;
for(int i = 0; i < words.size(); ++ i)
if(uss.find(words[i]) == uss.end() && exist(board, words, i))
uss.insert(words[i]);
vector<string> res;
for(auto it = uss.begin(); it != uss.end(); ++ it)
res.push_back(*it);
return res;
}
private:
bool exist(vector<vector<char>> &board, vector<string> &words, int k)
{
int n = board.size(), m = board[0].size();
if(n * m < words[k].size())
return false;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
if(board[i][j] == words[k][0] && DFS(board, i, j, words[k], 0))
return true;
}
bool DFS(vector<vector<char> > &board, int x, int y, string &word, int i)
{
if(i == word.size() - 1)
return true;
int n = board.size(), m = board[0].size();
board[x][y] = '#';
if ((x + 1 < n && board[x + 1][y] == word[i + 1] && DFS(board, x + 1, y, word, i + 1)) ||
(x - 1 >= 0 && board[x - 1][y] == word[i + 1] && DFS(board, x - 1, y, word, i + 1)) ||
(y + 1 < m && board[x][y + 1] == word[i + 1] && DFS(board, x, y + 1, word, i + 1)) ||
(y - 1 >= 0 && board[x][y - 1] == word[i + 1] && DFS(board, x, y - 1, word, i + 1)))
{
board[x][y] = word[i];
return true;
}
board[x][y] = word[i];
return false;
}
};
上面代码超时。接下来换种思路，既然对每个单词在board中查找超时，那么直接从board中开始查找，看看记录出现的单词呢？这样，就用到了前面题目给出的提示，即需要单词列表的前缀，也就是需要先对单词列表构造字典树（Trie树）。
然后，分别以board中的每一个字母为起始，在构造好的Trie树中进行查找，即递归对board中每个相邻字母在Trie树中对应的子树进行查找。
如果搜索到Trie树中某一节点的index不为-1，说明查找到单词，记录下来即可，同时需要标记其index为-1。
时间复杂度：O(???)
空间复杂度：O(???)
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct TrieNode
{
TrieNode *next[26];
int index;
TrieNode(int i = -1)
{
memset(next, 0, sizeof(next));
index = i;
}
};
class Solution
{
vector<string> res;
public:
vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
{
if(board.size() == 0 || board[0].size() == 0 || words.size() == 0)
return res;
TrieNode *root = new TrieNode();
for(int i = 0; i < words.size(); ++ i)
insert(root, words[i], i);
for(int i = 0; i < board.size(); ++ i)
for(int j = 0; j < board[0].size(); ++ j)
findWords(board, i, j, root, words);
return res;
}
private:
void insert(TrieNode *root, string &s, int index)
{
for(int i = 0; i < s.size(); ++ i)
{
if(root -> next[s[i] - 'a'] == NULL)
root -> next[s[i] - 'a'] = new TrieNode();
root = root -> next[s[i] - 'a'];
}
root -> index = index;
}
void findWords(vector<vector<char>> &board, int x, int y,
TrieNode *root, vector<string> &words)
{
char c = board[x][y];
if(c == '#' || root -> next[c - 'a'] == NULL)
return;
if(root -> next[c - 'a'] -> index != -1)
{
res.push_back(words[root -> next[c - 'a'] -> index]);
root -> next[c - 'a'] -> index = -1;
}
board[x][y] = '#';
if(x + 1 < board.size())
findWords(board, x + 1, y, root -> next[c - 'a'], words);
if(x - 1 >= 0)
findWords(board, x - 1, y, root -> next[c - 'a'], words);
if(y + 1 < board[0].size())
findWords(board, x, y + 1, root -> next[c - 'a'], words);
if(y - 1 >= 0)
findWords(board, x, y - 1, root -> next[c - 'a'], words);
board[x][y] = c;
}
};