class Solution {
    final int[][] DIRS = {{-1, 0},  {1, 0}, {0, -1}, {0, 1}};
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
            // throw new illegalargumentexception("invalid input");
            return result;
        }
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        int rows = board.length;
        int cols = board[0].length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j, trie.root, sb, result, rows, cols);
            }
        }
        return result;
    }
    private void dfs(char[][] board, int x, int y, TrieNode cur, StringBuilder sb, List<String> result, int rows, int cols) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) {
            return;
        }
        char ch = board[x][y];
        if (ch == '#' || cur.children.get(ch) == null) {
            return;
        }
        board[x][y] = '#';
        TrieNode next = cur.children.get(ch);
        sb.append(ch);
        if (next.isEnd) {
            result.add(sb.toString());
            next.isEnd = false;
        }
        for (int[] dir : DIRS) {
            int neiX = x + dir[0];
            int neiY = y + dir[1];
            dfs(board, neiX, neiY, next, sb, result, rows, cols);
        }
        sb.deleteCharAt(sb.length() - 1);
        board[x][y] = ch;
    }
}
class Trie {
    TrieNode root;
    public Trie() {                    /** Initialize your data structure here. */
        root = new TrieNode();
    }
    public void insert(String word) {   /** Inserts a word into the trie. */
        if (word == null || word.length() == 0) {
            return;
        }
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            TrieNode next = cur.children.get(word.charAt(i));
            if (next == null) {
                next = new TrieNode();
                cur.children.put(word.charAt(i), next);
            }
            cur = next;
        }
        cur.isEnd = true;
    }
    public boolean search(String word) { /** Returns if the word is in the trie. */
        if (word == null || word.length() == 0) {
            return false;
        }
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            TrieNode next = cur.children.get(word.charAt(i));
            if (next == null) {
                return false;
            }
            cur = next;
        }
        return cur.isEnd;
    }
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return true;
        }
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            TrieNode next = cur.children.get(prefix.charAt(i));
            if (next == null) {
                return false;
            }
            cur = next;
        }
        return true;
    }
}
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
    public TrieNode() {}
}