leetcode 212. Word Search II | 212. 单词搜索 II（Trie，回溯，DFS）

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

基于前缀树实现，如果把 Trie 也看做一个特殊的图的话，就是 将两个图同时进行 dfs，就像判断两个树是否相同那样。

可以参考：leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java） 中的数据结构，然后改造一下即可。

class Node {
    Node[] map;
    boolean isEnd;

    public Node() {
        this.map = new Node['z' - 'a' + 1];
    }

    public Node get(char c) {
        return map[c - 'a'];
    }

    public Node put(char c) {
        Node node = new Node();
        map[c - 'a'] = node;
        return node;
    }
}

class Trie {
    Node node;

    public Trie() {
        node = new Node();
    }

    public void insert(String word) {
        char[] chars = word.toCharArray();
        Node cur = node;
        for (int i = 0; i < chars.length; i++) {
            if (cur.get(chars[i]) != null) {
                cur = cur.get(chars[i]);
            } else {
                cur = cur.put(chars[i]);
            }
            if (i == chars.length - 1) {
                cur.isEnd = true;
            }
        }
    }
}


class Solution {
    int M, N;
    List result;

    public List findWords(char[][] board, String[] words) {
        M = board.length;
        N = board[0].length;
        result = new ArrayList<>();

        Trie trie = new Trie();
        for (String s : words) {
            trie.insert(s);
        }
        boolean[][] visited = new boolean[M][N];
        for (int k = 0; k < trie.node.map.length; k++) {
            if (trie.node.map[k] == null) continue;
            // word can start from any location on board
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    dfs(board, i, j, visited, trie.node.map[k], (char) (k + 'a'), String.valueOf((char) (k + 'a')));
                }
            }
        }
        return result;
    }

    public void dfs(char[][] board, int i, int j, boolean[][] visited, Node node, char val, String path) {
        if (i < 0 || i == M || j < 0 || j == N || visited[i][j] || board[i][j] != val) return;
        if (node.isEnd) {
            result.add(path);
            node.isEnd = false; // 避免相同前缀的字符串被多次添加到result中
        }

        visited[i][j] = true;
        for (int k = 0; k < node.map.length; k++) {
            Node next = node.map[k];
            if (next != null) {
                dfs(board, i + 1, j, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                dfs(board, i - 1, j, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                dfs(board, i, j + 1, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
                dfs(board, i, j - 1, visited, next, (char) (k + 'a'), path + ((char) (k + 'a')));
            }
        }
        visited[i][j] = false;
    }
}