给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

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

import java.util.ArrayList;
import java.util.List;

class Solution {

    private static final int[] DX = {0, 1, 0, -1};

    private static final int[] DY = {1, 0, -1, 0};


    private static int solve(char[][] board, int row, int col, Trie.TrieNode root, List<String> ret, boolean[][] visited) {

        int p = board[row][col] - 'a';

        Trie.TrieNode node = root.children[p];

        if (node == null || node.pass == 0) {
            return 0;
        }

        int sum = 0;

        if (node.end > 0) {
            ret.add(node.word);
            node.end--;
            sum++;
        }

        for (int i = 0; i < 4; ++i) {
            int x = row + DX[i];
            int y = col + DY[i];
            if (x >= 0 && y >= 0 && x < board.length && y < board[0].length && !visited[x][y]) {
                visited[x][y] = true;
                sum += solve(board, x, y, node, ret, visited);
                visited[x][y] = false;
            }
        }

        node.pass -= sum;

        return sum;
    }

    public static List<String> findWords(char[][] board, String[] words) {
        if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
            return new ArrayList<>(0);
        }

        Trie trie = new Trie();
        trie.addAll(words);

        List<String> ret = new ArrayList<>();

        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                List<String> item = new ArrayList<>();
                boolean[][] visited = new boolean[board.length][board[0].length];
                visited[i][j] = true;
                solve(board, i, j, trie.getRoot(), item, visited);
                ret.addAll(item);
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        char[][] board = {{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
        String[] words = {"oath", "pea", "eat", "rain"};
        List<String> ret = findWords(board, words);
        ret.forEach(System.out::println);
    }
}

class Trie {

    private TrieNode root;

    static class TrieNode {
        int pass = 0;
        int end = 0;
        String word;
        TrieNode[] children = new TrieNode[26];
    }

    public Trie() {
        this.root = new TrieNode();
    }

    public TrieNode getRoot() {
        return root;
    }

    public void addAll(String[] words) {
        for (String word : words) {
            add(word);
        }
    }

    public void add(String str) {
        TrieNode cur = root;
        cur.pass++;
        for (int i = 0; i < str.length(); ++i) {
            int path = str.charAt(i) - 'a';
            if (cur.children[path] == null) {
                cur.children[path] = new TrieNode();
            }
            cur = cur.children[path];
            cur.pass++;
        }
        cur.end++;
        cur.word = str;
    }

}