题目：

给定一个 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 * 104 1 <= words[i].length <= 10 words[i] 由小写英文字母组成 words 中的所有字符串互不相同

思路：前缀树+dfs

如果给我们一个二维字符网格和一个字符串，然我们检查字符串是否在二维网格中出现，我们可以很容易写出，先遍历二维网格，如果有和字符串开头相同的字符则使用dfs查找是否存在。题目中给出的是一个字符串列表，我们需要考虑如何快速在这个列表中出以这个字符开头的字符串，显而易见我们可以使用字典序查找。

具体算法：

先构建一颗字典树 然后在使用dfs查找

class Solution {
          
   
    public class TrieTree{
          
   
        TrieTree[] next;
        String end;

        public TrieTree(){
          
   
            next = new TrieTree[26];
            end = null;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
          
   
        List<String> ans = new ArrayList<>();

        if(board.length == 0 || board[0].length == 0) return ans;

        TrieTree root = new TrieTree();
        TrieTree p = root;

        // 构建前缀树
        int n = words.length;
        for(int i = 0; i < n; i++) {
          
   
            p = root;
            for(int j = 0; j < words[i].length(); j++) {
          
   
                int ind = words[i].charAt(j) - a;
                if(p.next[ind] == null) p.next[ind] = new TrieTree();
                p = p.next[ind];
            }
            p.end = words[i];
        }

        n = board.length;
        int m = board[0].length;
        is = new boolean[n][m];
        for(int i = 0; i < n; i++) {
          
   
            for(int j = 0; j < m; j++) {
          
   
                if(root.next[board[i][j] - a] != null) {
          
   
                    check(root, board, i, j, ans, n, m);
                }
            }
        }

        return ans;
    }

    boolean[][] is;

    private void check(TrieTree root, char[][] board, int i, int j, List<String> ans, int n, int m) {
          
   
        if(i < 0 || j < 0 || i >= n || j >= m || is[i][j] || root.next[board[i][j] - a] == null) return;
        int ind = board[i][j] - a;
        if(root.next[ind].end != null) {
          
   
            ans.add(root.next[ind].end);
            root.next[ind].end = null;
        }
        is[i][j] = true;
        check(root.next[ind], board, i + 1, j, ans, n, m);
        check(root.next[ind], board, i - 1, j, ans, n, m);
        check(root.next[ind], board, i, j + 1, ans, n, m);
        check(root.next[ind], board, i, j - 1, ans, n, m);
        is[i][j] = false;
    }
}