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

回溯 + 剪枝 + 前缀树

利用前缀树的pass来保证不走重复路，不重复收集答案

// 前缀树节点
    public static class Node{
        Node[] nexts;
        int pass;
        int end;
        public Node(){
            nexts = new Node[26];
            pass = 0;
            end = 0;
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        //前缀树最顶端的头
        Node root = new Node();
        //构建前缀树
        for (String word : words) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                int path = word.charAt(i) - 'a';
                if (cur.nexts[path] == null) {
                    cur.nexts[path] = new Node();
                }
                cur = cur.nexts[path];
                cur.pass++;
            }
            cur.end++;
        }
        List<String> ans = new ArrayList<>();  // 答案
        // 沿途走过的字符，收集起来存在path里
        LinkedList<Character> path = new LinkedList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 每个位置出发的情况下，答案都收集
                dfs(board, i, j, path, root, ans);
            }
        }
        return ans;
    }
    /*
     * @param path 当前路径
     * @param cur 当前前缀树节点
     * @param ans 收集答案
     * @return 返回收集了几个字符串答案(为了不重复收集答案用)
     */
    public int dfs(char[][] board, int row, int col, LinkedList<Character> path, Node cur, List<String> ans) {
        char c = board[row][col];
        if (c == 0) {  // 这个位置之前走过，不走回头路
            return 0;
        }
        int index = c - 'a';
        /* 剪枝
        1. 前缀树没路可走  2. 从当前位置往下的答案都收集过了，不走重复路，不重复收集*/
        if ( cur.nexts[index] == null || cur.nexts[index].pass == 0){
            return 0;
        }
        cur = cur.nexts[index];
        path.add(c);
        int count = 0;  //收集了多少个答案
        if (cur.end > 0) {
            char[] str = new char[path.size()];
            int i = 0;
            for (char p : path) {
                str[i++] = p;
            }
            ans.add(String.valueOf(str));
            cur.end--; // 防止重复收集答案
            count++;
        }
        // 增加现场， 不走回头路机制
        board[row][col] = 0;
        if (row > 0) {
            count += dfs(board, row - 1, col, path, cur, ans);
        }
        if (row < board.length - 1) {
            count += dfs(board, row + 1, col, path, cur, ans);
        }
        if (col > 0) {
            count += dfs(board, row, col - 1, path, cur, ans);
        }
        if (col < board[0].length - 1) {
            count += dfs(board, row, col + 1, path, cur, ans);
        }
        // 恢复现场
        board[row][col] = c;
        // 恢复现场
        path.pollLast();
        cur.pass -= count;
        return count;
    }