题目：
Given a 2D board and a list of words from the dictionary, find allwords in the board.Each word must be constructed from letters of sequentially adjacentcell, where “adjacent” cells are those horizontally or verticallyneighboring. The same letter cell may not be used more than once in aword.Example:
Input: words = [“oath”,”pea”,”eat”,”rain”] and board = [[‘o’,’a’,’a’,’n’], [‘e’,’t’,’a’,’e’], [‘i’,’h’,’k’,’r’], [‘i’,’f’,’l’,’v’] ]
Output: [“eat”,”oath”] Note: You may assume that all inputs areconsist of lowercase letters a-z.
这道题是 79 题 word search 的 follow up，如果按照那道题的做法我们在二维数组中寻找每一个单词那么一定会超时，因为每个单词都要搜索一次会产生很多重复搜索，所以我们想到的是从头到尾遍历二维数组，在遍历过程中 dfs，那么在这个过程中一定把所有可能组成的单词都遍历了一遍，所以我们想到可以用一个 hashset 来存储需要搜索的单词，然后在 dfs 过程中把每个产生的单词在 hashset 中寻找。代码如下：
class Solution {
List<String> res = new ArrayList<>();
HashSet<String> set = new HashSet<>();
boolean[][] visited;
public List<String> findWords(char[][] board, String[] words) {
visited = new boolean[board.length][board[0].length];
for (String word : words)
set.add(word);
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[0].length; j ++) {
dfs(board, “”, i, j);
}
}
return res;
}
public void dfs(char[][] board, String cur, int x, int y) {
if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y])
return;
char c = board[x][y];
if (set.contains(cur+c)) {
res.add(cur+c);
set.remove(cur+c);
}
visited[x][y] = true;
dfs(board, cur+c, x+1, y);
dfs(board, cur+c, x-1, y);
dfs(board, cur+c, x, y+1);
dfs(board, cur+c, x, y-1);
visited[x][y] = false;
}
}
但不幸的是这种方法还是会超时，所以我们想能否有种方法能让我们提前结束 backtrack 呢，如果在所有单词中都没有这个前缀我们就可以提前结束 backtarcking。因此想到可以用 Trie 来实现，代码如下：
class Solution {
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
public TrieNode() {}
}
TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode p = root;
for (char c : word.toCharArray()) {
if (p.next[c-‘a’] == null)
p.next[c-‘a’] = new TrieNode();
p = p.next[c-‘a’];
}
p.word = word;
}
return root;
}
List<String> res = new ArrayList<>();
boolean[][] visited;
public List<String> findWords(char[][] board, String[] words) {
visited = new boolean[board.length][board[0].length];
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i ++) {
for (int j = 0; j < board[0].length; j ++) {
if (root.next[board[i][j]-‘a’] == null) continue;
dfs(board, root, i, j);
}
}
return res;
}
public void dfs(char[][] board, TrieNode node, int x, int y) {
if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y])
return;
char c = board[x][y];
if (node.next[c-‘a’] == null) return;
if (node.next[c-‘a’].word != null) {
res.add(node.next[c-‘a’].word);
// 如果找到了这个单词就把它设成 null，避免重复的结果
node.next[c-‘a’].word = null;
}
visited[x][y] = true;
dfs(board, node.next[c-‘a’], x+1, y);
dfs(board, node.next[c-‘a’], x-1, y);
dfs(board, node.next[c-‘a’], x, y+1);
dfs(board, node.next[c-‘a’], x, y-1);
visited[x][y] = false;
}
}