作者：Grey
原文地址：单词搜索系列问题
LeetCode 79. 单词搜索
总体思路是：枚举从board的每个位置开始，看能否走出给定的单词，伪代码如下：
for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (p(i, j, 0, str, board)) { return true; } } } 递归函数p表示从board[i][j]开始，能否走出str从0位置开始到最后的字符串。如果有任意一个路径满足条件，直接返回true即可。递归函数p的base case是：
public static boolean p(int i, int j, int index, char[] str, char[][] board) { if (index == str.length) { return true; } if (i >= board.length || j >= board[0].length || i < 0 || j < 0 ) { return false; } if (board[i][j] == '0') { return false; } ...... } 第一个if表示，如果index已经到str结尾了，说明我已经完成了str的完全匹配，直接返回true即可。
第二个if表示，如果index还没到str的结尾位置，但是i，j位置越界了，说明我的决策有问题，直接返回false。
第三个if表示，如果我当前的位置是曾经走过的位置，返回false。（因为我们为了防止走回头路，将走过的位置都标识为了0字符）
经过三个if，就是主要逻辑：
public static boolean p(int i, int j, int index, char[] str, char[][] board) { ....... char c = board[i][j]; board[i][j] = '0'; if (str[index] == c) { boolean p1 = p(i + 1, j, index + 1, str, board); if (p1) { board[i][j] = c; return true; } boolean p2 = p(i, j + 1, index + 1, str, board); if (p2) { board[i][j] = c; return true; } boolean p3 = p(i - 1, j, index + 1, str, board); if (p3) { board[i][j] = c; return true; } boolean p4 = p(i, j - 1, index + 1, str, board); if (p4) { board[i][j] = c; return true; } } board[i][j] = c; return false; } 首先，将当前位置标识为了已走过，即
board[i][j] = '0' 接下来，只有在
str[index] == c 条件下（即：我当前位置需要匹配的字符正好是遍历到位置的字符），我才需要走四个方向的分支，四个分支，只要有一个分支完成任务，则无须走其他分支，直接返回true，四个分支都是false，则返回false。
完整代码见：
public class LeetCode_0079_WordSearch { // 不能走重复路 public static boolean exist(char[][] board, String word) { char[] str = word.toCharArray(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (p(i, j, 0, str, board)) { return true; } } } return false; } public static boolean p(int i, int j, int index, char[] str, char[][] board) { if (index == str.length) { return true; } if (i >= board.length || j >= board[0].length || i < 0 || j < 0 ) { return false; } if (board[i][j] == '0') { return false; } char c = board[i][j]; board[i][j] = '0'; if (str[index] == c) { boolean p1 = p(i + 1, j, index + 1, str, board); if (p1) { board[i][j] = c; return true; } boolean p2 = p(i, j + 1, index + 1, str, board); if (p2) { board[i][j] = c; return true; } boolean p3 = p(i - 1, j, index + 1, str, board); if (p3) { board[i][j] = c; return true; } boolean p4 = p(i, j - 1, index + 1, str, board); if (p4) { board[i][j] = c; return true; } } board[i][j] = c; return false; } } LeetCode 212. 单词搜索 II
总体思路是：枚举从board的每个位置开始，看能走出哪些单词表中的单词，伪代码如下：
for (int i = 0; i < board.length;i++) { for (int j = 0; j < board[0].length;j++) { int size = process(i,j, board, words); if (size == words.size) { return new ArrayList<>(words); } } } 递归函数process 表示从board[i][j]出发，能走出哪些单词表中的单词。返回值是能走出的单词数量是多少，如果返回值正好等于单词表的数量，不需要继续尝试了，直接返回可以走出所有单词。
如果要达到上述目的，这个递归函数还差哪些参数呢？
首先，我需要一个List<String> ans来存储所有走出的单词是哪些；
其次，我需要一个变量List<Character> pre存储我每次走到的字符串是什么；
最后，我需要一个快速判断走的是不是无效路径的数据结构，因为如果我没有这个数据结构，我每走一步都需要暴力枚举我走出的pre是不是在单词表中。例如，假设单词表为：
[apple, banana] 假设一个3 x 5的board为：
['a','p','p','l','e'] ['a','x','y','b','a'] ['b','a','n','a','n'] 如果我即将走的下一个字符是第二行第二列的x字符，这个数据结构可以快速帮我过滤掉这种情况，没必要从x字符继续往下走了。
这个数据结构就是前缀树，通过前缀树，可以很快找到某个字符串是否是一个单词的前缀，同时，也可以很快得出某个字符串是否已经完成了匹配。
完善后的递归函数完整签名如下：
// 从board的i，j位置出发， // 走过的路径保存在pre中， // 收集到的单词表中的单词保存在ans中 // trie就是单词表建立的前缀树 int process(int i, int j, LinkedList<Character> pre, List<String> ans, char[][] board, Trie trie) 在整个递归调用之前，我们需要最先构造前缀树，前缀树的定义如下：
public static class Trie { public Trie[] next; public int pass; public boolean end; public Trie() { // 由于只有26个小写字母，所以只需要准备26大小的数组即可。 next = new Trie[26]; // 遍历过的字符次数 pass = 0; // 是否是一个字符串的结尾 end = false; } } 针对单词表，我们建立前缀树，过程如下：
Set<String> set = new HashSet<>(); Trie trie = new Trie(); for (String word : words) { if (!set.contains(word)){ set.add(word); buildTrie(trie,word); } } 之所以要定义Set，是因为想把单词表去重，buildTrie的完整代码如下，以下为前缀树创建的经典代码，有路则复用，无路则创建，循环结束后，将end设置为true，表示这个单词的结束标志：
private static void buildTrie(Trie trie, String word) { char[] str = word.toCharArray(); for (char c : str) { if (trie.next[c - 'a'] == null) { trie.next[c - 'a'] = new Trie(); } trie = trie.next[c - 'a']; trie.pass++; } trie.end = true; } 任何一个字符x，如果：
trie.next[x - 'a'] == null || trie.next[x - 'a'].pass == 0; 则表示没有下一个方向上的路，或者下一个方向上的字符已经用过了，这种情况下，就直接可以无需继续从这个字符开始尝试。
到了某个字符，如果：
trie.end = true 表示这个字符已经是满足条件的某个单词的结尾了，可以开始收集答案。
前缀树准备好了以后，就可以考虑递归函数的base case了，
public static int process(int i, int j, LinkedList<Character> pre, List<String> ans, char[][] board, Trie trie){ if (i >= board.length || i < 0 || j >= board[0].length || j < 0) { return 0; } if (board[i][j] == '0') { // 不走回头路 return 0; } if (trie.next[board[i][j] - 'a'] == null || trie.next[board[i][j] - 'a'].pass == 0) { // 没有路可以走 return 0; } ... } 第一个if表示越界，显然返回0，因为你的决策已经让i，j越界了，决策错了，返回0没毛病。
第三个if表示的情况，就是前面说的，前缀树判断当前位置已经没有继续尝试的必要了，返回0也没毛病。
由于题目要求不能走回头路，所以我将走过的位置上的字符修改为字符0，标识我走过这里了，所以第二个if表示：如果我们决策到某个位置是0,说明我们走了回头路，返回0也没毛病。
如果顺利通过了上述三个if，那么说明当前决策的位置有利可图，说不定就可以走出单词表中的单词，所以把当前位置的字符加入pre,表示我已经选择了当前字符，请去上下左右四个方向帮我收集答案，代码如下：
pre.addLast(c); trie = trie.next[index]; int fix = 0; if(trie.end) { ans.add(buildString(pre)); trie.end=false; fix++; } // 这句表示：先标识一下当前位置为0字符，表示我已经走过了 board[i][j] = '0'; // 以下四行表示： // 请去上，下，左，右四个方向帮我收集答案吧。 fix +=process(i+1,j,pre,ans,board,trie); fix+=process(i,j+1,pre,ans,board,trie); fix+=process(i-1,j,pre,ans,board,trie); fix+=process(i,j-1,pre,ans,board,trie); // 深度优先遍历的恢复现场操作。 board[i][j] = c; pre.pollLast(); trie.pass-=fix; 其中if(trie.end)说明已经走出了一个符合条件的单词，可以收集答案了。buildString(pre)就是把之前收集的字符拼接成一个字符串，代表已经拼凑出来的那个单词：
private static String buildString(LinkedList<Character> pre) { LinkedList<Character> preCopy = new LinkedList<>(pre); StringBuilder sb = new StringBuilder(); while (!preCopy.isEmpty()) { Character c = preCopy.pollFirst(); sb.append(c); } return sb.toString(); } 完整代码如下：
public class LeetCode_0212_WordSearchII { public static class Trie { public Trie[] next; public int pass; public boolean end; public Trie() { next = new Trie[26]; pass = 0; end = false; } } public static List<String> findWords(char[][] board, String[] words){ Set<String> set = new HashSet<>(); Trie trie = new Trie(); for (String word : words) { if (!set.contains(word)){ set.add(word); buildTrie(trie,word); } } LinkedList<Character> pre= new LinkedList<>(); List<String> ans = new ArrayList<>(); for (int i = 0; i < board.length;i++) { for (int j = 0; j < board[0].length;j++) { int times = process(i,j,pre,ans,board,trie); if (times == set.size()) { return new ArrayList<>(set); } } } return ans; } public static int process(int i, int j, LinkedList<Character> pre, List<String> ans, char[][] board, Trie trie){ if (i >= board.length || i < 0 || j >= board[0].length || j < 0) { return 0; } char c = board[i][j]; if (c == '0') { // 不走回头路 return 0; } int index= c - 'a'; if (trie.next[index] == null || trie.next[index].pass == 0) { // 没有路可以走 return 0; } pre.addLast(c); trie = trie.next[index]; int fix = 0; if(trie.end) { ans.add(buildString(pre)); trie.end=false; fix++; } board[i][j] = '0'; fix +=process(i+1,j,pre,ans,board,trie); fix+=process(i,j+1,pre,ans,board,trie); fix+=process(i-1,j,pre,ans,board,trie); fix+=process(i,j-1,pre,ans,board,trie); board[i][j] = c; pre.pollLast(); trie.pass-=fix; return fix; } private static String buildString(LinkedList<Character> pre) { LinkedList<Character> preCopy = new LinkedList<>(pre); StringBuilder sb = new StringBuilder(); while (!preCopy.isEmpty()) { Character c = preCopy.pollFirst(); sb.append(c); } return sb.toString(); } private static void buildTrie(Trie trie, String word) { char[] str = word.toCharArray(); for (char c : str) { if (trie.next[c - 'a'] == null) { trie.next[c - 'a'] = new Trie(); } trie = trie.next[c - 'a']; trie.pass++; } trie.end = true; } } 
