😁212 word search II

https://leetcode.com/problems/word-search-ii/

你依然得从每个cell开始都做一遍dfs，但是如果只用dfs你遇到一个word就得返回，没法一次性遍历完路径上的所有word，所以要借用trie tree跟着一起做dfs，直到trie tree node为空才返回，注意build trie tree不是个递归的过程，还有就是trie tree是有点错层的，它的root是个dummy node，所以你得进来就先进下一层

还有对dfs来说所有操作都在本层里对本层的数据做的，包括检查valid，sb.append，检查是否是word，要做到进入dfs之前不需要提前检查下一层数据这样你才对端了

class Solution {
    private Set<String> ans = new HashSet<>();
    private static int[][] DIR = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    class TrieNode {
        boolean isWord;
        TrieNode[] next;
        public TrieNode() {
            isWord = false;
            next = new TrieNode[26];
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        int n = board[0].length;
        TrieNode root = buildTrieTree(words);
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
              dfs(board, visited, i, j, root, new StringBuilder());
          }
        }
        
        return new ArrayList<>(ans);
    }
    private void dfs(char[][] board, boolean[][] visited, int i, int j, TrieNode root, StringBuilder sb) {
        if (!isValid(board, visited, i, j)) return;
        if (root == null) return;
        // 因为trienode的root是个dummy root，进来先进下一层这里才是本层对应的node，有点别扭 我知道
        root = root.next[board[i][j] - 'a'];
        // 提前return省点内存，你也可以去下一层之后再return，但是下面检查isWord就要先判断是不是为null
        if (root == null) return;
        
        sb.append(board[i][j]);
        if (root.isWord) ans.add(sb.toString());
        // visited是重复利用的所以记得要吐
        visited[i][j] = true;
        for (int[] dir : DIR) {
            int x = i + dir[0];
            int y = j + dir[1];
            dfs(board, visited, x, y, root, sb);
        }
        sb.deleteCharAt(sb.length() - 1);
        visited[i][j] = false;
    }
    private boolean isValid(char[][] board, boolean[][] visited, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        //记得valid和visited是相反的
        return !visited[i][j];
    }
    private TrieNode buildTrieTree(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode cur = root;
            char[] array = word.toCharArray();
            for (char ch : array) {
                int idx = ch - 'a';
                if (cur.next[idx] == null) {
                    cur.next[idx] = new TrieNode();
                }
                cur = cur.next[idx];
            }
            cur.isWord = true;
        }
        return root;
    }
}