这真的是一道高频题。我叫它甚高频，因为我有一次，周一电面被问到，周二电面又被问到。
这题Trie的操作要熟，基本功，基本功，基本功。 重要的事情说三遍。
DFS的base case,
每次进入base case时不知道我能不能match这个点。
进入base case时我手上的是我root那个点，和我要match的这个字母。
我这里还不知道我这个字母在不在root的child里面,
如果在了，那么我下降一格。一定要记得下降一格。
如果不在，那儿直接返回， 就没下面的事了。
下降一层之后要做的事有，看这个是不是个单词的结尾。
然后再站在上帝视角，看它的邻居。

class Solution {
    int N, M;
    int[][] OFFSETS;
    public List<String> findWords(char[][] board, String[] words) {
        N = board.length;
        M = board[0].length;
        OFFSETS = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        TrieNode root = new TrieNode('a');
        for (int i = 0; i < words.length; i++) {
            addToTrie(root, words[i], i);
        }
        Set<String> ans = new HashSet<>();
        boolean[][] visited = new boolean[N][M];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                explore(board, r, c, words, root, visited, ans);        
            }
        }
        return new ArrayList<>(ans);
    }
    private void explore(char[][] board, int r, int c, String[] words, 
                         TrieNode root, boolean[][] visited, Set<String> ans) {
        //base case
        if (root == null) return;
        if (root.get(board[r][c]) == null) return;
        root = root.get(board[r][c]); //下移一格
        if (root.isWord) ans.add(words[root.id]);
        visited[r][c] = true;
        
        for (int[] os : OFFSETS) {
            int nr = os[0] + r, nc = os[1] + c;
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (visited[nr][nc]) continue;
            explore(board, nr, nc, words, root, visited, ans);
        }
        visited[r][c] = false; //记得撤回 
        return;
    }
    private void addToTrie(TrieNode node, String word, int id) {
        for (int i = 0; i < word.length(); i++) {
            node = node.getOrCreate(word.charAt(i));
        }
        node.isWord = true;
        node.id = id;
    }
}

class TrieNode {
    char c;
    boolean isWord;
    int id;
    TrieNode[] children;
    public TrieNode(char c) {
        this.c = c;
        this.children = new TrieNode[26];
    }
    public TrieNode getOrCreate(char ch) {
        if (get(ch) == null) {
            children[ch - 'a'] = new TrieNode(ch);
        }
        return get(ch);
    }
    public TrieNode get(char c) {
        return children[c - 'a'];
    }
}