05 August 2008
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.
Example:
1
2
3
4
5
6
7
8
9
10
Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
这道题意思就是从二维数组中某个字符出发，可以向左向右向上向下移动，走过的路径构成一个字符串，判断是否能走出给定字符串的 word ，走过的字符不能够再走第二次。比如 eat，从第二行最后一列的 e 出发，向左移动，再向左移动，就走出了 eat。题目中给一个 word 列表，要求找出里面哪些单词可以由 board 生成。
1) 第79 题Word Search是判断某个单词能否在 board 中生成，所以暴力解法可以是遍历这道题给出的words的所有单词，每个单词都用79题的DFS的办法来看能不能被生成。
2) Trie前缀树，这里是LC的思路。
上面的解法的核心思想是从 words 中依次1
选定一个单词 -> 从图中的每个位置出发，看能否找到这个单词
1
从二维数组中的每个位置出发 -> 看遍历过程中是否遇到了 words 中的某个单词
想知道遍历过程中判断是否遇到了某个单词，可以事先把所有单词存到前缀树中。这样的话，如果当前走的路径不是前缀树的前缀，就可以提前结束了，而如果是前缀树的中的单词，就将其存到结果中。
关于实现，可以在遍历过程中，将当前路径的单词传进函数，然后判断当前路径构成的单词是否是在前缀树中出现，这个想法可行，但不够好（是上面方法1把DFS换成了Trie），因为每次都从前缀树中判断当前路径的单词，会带来重复的判断。比如先判断了 pan 存在于前缀树中，接下来假如路径变成 panda ，判断它在不在前缀树中，又需要判断一遍 pan 。
因此，可以把前缀树用递归中来传递前缀树的节点，判断当前节点的孩子是否为 null，如果是 null 说明当前的前缀不存在，可以提前结束。如果不是 null，再判断当前节点是否是单词的结尾，如果是结尾直接将当前单词加入。由于递归过程中没有加路径，所以我们改造一下前缀树的节点，将单词直接存入节点，这样的话就可以直接取到了。
79题代码套过来的暴力解法，可以accept
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 List<String> findWords(char[][] board, String[] words) {
List<String> results = new ArrayList<>();
for (String word : words) {
if (exist(board, word)) {
results.add(word);
}
}
return results;
}
// 下面的代码是把79题的代码抄过来，判断每个单词是否能够被生成
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
int rows = board.length;
int cols = board[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (dfs(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, String word, int index) {
if (index == word.length()) {
return true;
}
int m = board.length;
int n = board[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(index)) {
return false;
}
char temp = board[i][j];
board[i][j] = '#';
boolean result = dfs(board, i + 1, j, word, index + 1) ||
dfs(board, i - 1, j, word, index + 1) ||
dfs(board, i, j + 1, word, index + 1) ||
dfs(board, i, j - 1, word, index + 1);
board[i][j] = temp; // 这步不能忘记，检查完当前起点为止的字符串后要恢复访问记录
return result;
}
}
Trie解法，具体步骤：
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class Solution {
// ------------------
class Trie {
private boolean is_word;
private Trie[] next;
/** Initialize your data structure here. */
public Trie() {
next = new Trie[26];
is_word = false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie root = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (root.next[ch - 'a'] == null) {
root.next[ch - 'a'] = new Trie();
}
root = root.next[ch - 'a'];
}
root.is_word = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
if (find(word) == null) {
return false;
}
return find(word).is_word;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return find(prefix) == null ? false : true;
}
private Trie find(String str) {
Trie root = this;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (root.next[ch - 'a'] == null) {
return null;
}
root = root.next[ch - 'a'];
}
return root;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
//------------------- 以上是构建Trie的代码
//O(m * n * h) - h为Trie的高度
Trie root = new Trie();
List<String> results;
public List<String> findWords(char[][] board, String[] words) {
results= new ArrayList<>();
if (board == null || board.length == 0 || board[0].length == 0 || words == null) {
return results;
}
int rows = board.length, cols = board[0].length;
// 1. 构建Trie并加入单词
for (String word : words) {
root.insert(word);
}
// 2. 对board中的每一个字符进行dfs，查找以该字符为起始是否是一个单词
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
StringBuilder sb = new StringBuilder();
// 这里额外空间可以传入一个记录visited的board，下面不用改成'#'也行
dfs(i, j, board, sb);
}
}
return results;
}
private void dfs(int i, int j, char[][] board, StringBuilder sb) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#') {
return;
}
sb.append(board[i][j]);
char temp = board[i][j];
board[i][j] = '#';
if (root.search(sb.toString())) {
if (!results.contains(sb.toString())) {
results.add(sb.toString());
}
}
if (root.startsWith(sb.toString())) {
// board中四个方向的dfs
dfs(i - 1, j, board, sb);
dfs(i + 1, j, board, sb);
dfs(i, j - 1, board, sb);
dfs(i, j + 1, board, sb);
}
sb.deleteCharAt(sb.length() - 1); //Trie中的路径
board[i][j] = temp;
}
}