从零学算法212

212.给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
输出：[“eat”,“oath”]
示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
输出：[]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10⁴
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

• 这里我首先想到的是遍历所有 words，然后再遍历所有 board 尝试每个字符作为起点能否得到某个 word，但是超时了，这里可以转换思路，遍历所有 board，得到以每个字符开始，组成字符串的所有可能性，然后看是否在 words 中，是就加入结果列表 res

•   // 方向数组
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    char[][] board;
    int m,n;
    // 存储 words 中的 word
    Set<String> set = new HashSet<>();
    // 记录 board 中每个字符是否已使用
    boolean[][] visit = new boolean[12][12];
    // 结果列表
    List<String> res = new ArrayList<>();
    public List<String> findWords(char[][] _board, String[] words) {
        board = _board;
        m= board.length;n= board[0].length;
        for(String s:words)set.add(s);
        StringBuilder sb = new StringBuilder();
        // 尝试所有字符为起点得到可能的路径
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                visit[i][j]=true;
                sb.append(board[i][j]);
                dfs(i,j,sb);
                visit[i][j] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return res;
    }
    void dfs(int i, int j, StringBuilder sb) {
    	// 因为 word 长度至多为 10 所以再往后就不找了
        if(sb.length() > 10)return;
        // 当前路径在 set 中就得到一个结果，记得去除 set 中该路径
        if(set.contains(sb.toString())){
            res.add(sb.toString());
            set.remove(sb.toString());
        }
        for(int[] d : dirs){
            int x = i + d[0];int y = j + d[1];
            if(x < 0 || x >= m || y < 0 || y >= n)continue;
            if(visit[x][y])continue;
            visit[x][y] = true;
            sb.append(board[x][y]);
            dfs(x, y, sb);
            visit[x][y] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
  

• 上述解法只在当前搜索路径达到 10 才进行剪枝，为了优化为每一步搜索都剪枝，我们可以使用前缀树（Trie），可以参考力扣 208 题的题解，我也趁此学习完记录了一下。该题解原文中也包含了前缀树的讲解。
• 这里我们把 isEnd 直接替换为一个 String 类型的变量 s，记录该尾字符对应的字符串。我们创建一个前缀树，将 word 都存入其中，然后遍历 borad 每个字符作为起点，如果前缀树的根节点的子节点都不包含该字符，那就都不用 dfs 了直接下一位。
• dfs 过程如果遇到了 s 不为 null 的情况，表示 board 存在路径对应 s（也就是 word），那就加入 set，因为 dfs 过程中可能不止一次找到该字符串，所以先用 set 记录，最后遍历添加到 res 即可。

•   class Solution {
        class TrieNode {
            String s;
            TrieNode[] tns = new TrieNode[26];
        }
        void insert(String s) {
            TrieNode p = root;
            for (char c:s.toCharArray()) {
                int u = c - 'a';
                if (p.tns[u] == null) p.tns[u] = new TrieNode();
                p = p.tns[u];
            }
            p.s = s;
        }
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        char[][] board;
        int m,n;
        Set<String> set = new HashSet<>();
        boolean[][] visit = new boolean[12][12];
        List<String> res = new ArrayList<>();
        TrieNode root = new TrieNode();
        public List<String> findWords(char[][] _board, String[] words) {
            board = _board;
            m= board.length;n= board[0].length;
            for(String s:words)insert(s);
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    int u = board[i][j] - 'a';
                    // 前缀树中有字符串以当前字符开头才寻找路径
                    if(root.tns[u] != null){
                        visit[i][j]=true; 
                        dfs(i,j,root.tns[u]);
                        visit[i][j] = false;
                    }
                }
            }
            for(String s:set)res.add(s);
            return res;
        }
        void dfs(int i, int j, TrieNode node) {
        	  // 因为每一步都合法，所以只要能找到这一步就加入 set
            if(node.s != null)set.add(node.s);
            for(int[] d : dirs){
                int x = i + d[0];int y = j + d[1];
                if(x < 0 || x >= m || y < 0 || y >= n)continue;
                if(visit[x][y])continue;
                int u = board[x][y] - 'a';
                // 之前是写死了长度大于 10 则停止搜索
                // 而这里只要当前字符不在 word 的需求中就停止搜索
                // 比如 words 为 [abcd,accd,adcd]，当前字符搜索到了前缀树第二层
                // 前缀树第二层包含了 [b,c,d]，可如果当前字符是比如 e，那就不需要再找了
                // ae*** 无论如何都不会在 words 中
                if(node.tns[u] != null){
                    visit[x][y] = true;
                    dfs(x, y, node.tns[u]);
                    visit[x][y] = false;
                }
            }
        }
    }