212. 单词搜索 II
思路
本题我起初想对每个输入串进行回溯搜索，但是这样会超时，最坏时间复杂度为3*10^4*4^10，复杂度过大。从这题也可以学到，对于问题进行时间复杂度进行粗略分析是必要的。
观察题目输入，m和n都不大于12，如果我们遍历每个单元格，以此为起点进行dfs回溯搜索，直到搜索长度大于10为止，其最坏时间复杂度为m*n*4^10，相比之前的算法减小了很多，是可行的。
但是这样显然还有优化的空间，如果我们搜索到的字符串不为任何目标串的前缀，我们就不需要继续搜索下去了。而这样自然而然地就需要用到Trie树。
有了目标字符串构建的trie树之后，我们就可以在树上进行遍历，只在当前方向是某个目标串的子串时才前进。
Trie树
本题的Trie树用来剪枝。
我们需要保存两个关键的东西，一个是其子节点列表（在本题是小写字母的情况下，就是26个子节点），另一个是当前节点所表示的字符串。我们需要知道当前节点保存的字符串，是因为这样我们可以快速地把这个串加入到答案搜索到的串中。
Trie树的一个关键方法是插入字符串，这个是必须实现的。其他的操作，例如查询字符串是否在树中出现，可以因题目而定。
例如在本题中，由于我们可以直接在树上进行回溯，就不需要单独写一个这个函数。
Code
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
| class Solution {
class TrieNode {
String s;
TrieNode[] tns = new TrieNode[26];
}
void insert(String s) {
TrieNode p = root;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (p.tns[u] == null) p.tns[u] = new TrieNode();
p = p.tns[u];
}
p.s = s;
}
Set<String> set = new HashSet<>();
char[][] board;
int n, m;
TrieNode root = new TrieNode();
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
boolean[][] vis = new boolean[15][15];
public List<String> findWords(char[][] _board, String[] words) {
board = _board;
m = board.length; n = board[0].length;
for (String w : words) insert(w);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int u = board[i][j] - 'a';
if (root.tns[u] != null) {
vis[i][j] = true;
dfs(i, j, root.tns[u]);
vis[i][j] = false;
}
}
}
List<String> ans = new ArrayList<>();
for (String s : set) ans.add(s);
return ans;
}
void dfs(int i, int j, TrieNode node) {
if (node.s != null) set.add(node.s);
for (int[] d : dirs) {
int dx = i + d[0], dy = j + d[1];
if (dx < 0 || dx >= m || dy < 0 || dy >= n) continue;
if (vis[dx][dy]) continue;
int u = board[dx][dy] - 'a';
if (node.tns[u] != null) {
vis[dx][dy] = true;
dfs(dx, dy, node.tns[u]);
vis[dx][dy] = false;
}
}
}
}
|
