import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class WordSearchII {
private class Trie {
Trie[] nodes = new Trie[26];
String word;
}
private void buildTrie(Trie trie, String word) {
for (int i = 0; i < word.length(); i++) {
if (trie.nodes[word.charAt(i) - 'a'] == null) {
trie.nodes[word.charAt(i) - 'a'] = new Trie();
}
trie = trie.nodes[word.charAt(i) - 'a'];
}
trie.word = word;
}
/**
* 这里相对第一题来说用到了set保存中间结果，而不是直接exist，原因在于假如trie中有ab和abb，则dfs的时候
* 遇到ab就会返回true了，那么abb永远不会走到，所以我们要dfs到trie结束为止
*/
public List findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
buildTrie(trie, word);
}
Set set = new HashSet();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(set, board, i, j, trie);
}
}
return new LinkedList(set);
}
/**
* 这里容易错的两点
* 1. if (c < 'a' || c > 'z') 这个容易掉了
* 2. 要用Set查重，别直接List
*/
private void dfs(Set set, char[][] board, int i, int j, Trie trie) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
return;
}
if (trie == null) {
return;
}
char c = board[i][j];
/**
* 这里千万不能掉了
*/
if (c < 'a' || c > 'z') {
return;
}
trie = trie.nodes[c - 'a'];
if (trie == null) {
return;
}
if (trie.word != null) {
set.add(trie.word);
/**
* 这里还不能return，比如当前是aa，但是还有aab，所以需要继续dfs
*/
}
board[i][j] ^= '#';
dfs(set, board, i + 1, j, trie);
dfs(set, board, i - 1, j, trie);
dfs(set, board, i, j + 1, trie);
dfs(set, board, i, j - 1, trie);
board[i][j] ^= '#';
}
}