单词搜索

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    int[][] directs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static class Node{
        Node[] next;
        boolean isEnd;
        public Node(){
            this.next = new Node[26];
            this.isEnd = false;
        }
    }
    Node root = null;
    char[][] board;
    boolean[][] access;
    List<String> result;
    public void createTri(String[] words){
        this.root = new Node();
        for(String word : words){
            Node cur = root;
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(cur.next[c - 'a'] == null){
                    cur.next[c - 'a'] = new Node();
                }
                cur = cur.next[c - 'a'];
                if(i == word.length() - 1){
                    cur.isEnd = true;
                }
            }
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        createTri(words);
        this.board = board;
        this.access = new boolean[board.length][board[0].length];
        this.result = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                dfs(i, j, root, temp);
            }
        }
        return result;
    }
    public void dfs(int i, int j, Node cur, StringBuilder temp){
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || 
        access[i][j] || cur.next[board[i][j] - 'a'] == null){
            return;
        }
        cur = cur.next[board[i][j] - 'a'];
        access[i][j] = true;
        temp.append(board[i][j]);
        if(cur.isEnd){
            cur.isEnd = false; // 找到一个单词就删一个 防止重复
            result.add(temp.toString());
        }
        for(int[] direct : directs){
            dfs(i + direct[0], j + direct[1], cur, temp);
        }
        temp.deleteCharAt(temp.length() - 1);
        access[i][j] = false;
    }
}