单词搜索问题

作者：Grey

原文地址：单词搜索问题

题目链接

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;   }}

更多

算法和数据结构笔记