class Solution {
    
    List<String> res = new ArrayList<>();
    
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root);
            }
        }
        
        return res;
    }

    public void dfs(char[][] board, int i, int j, TrieNode p) {
        char c = board[i][j];
        
        if (c == '#' || p.next[c - 'a'] == null) return;
        
        p = p.next[c - 'a'];
        if (p.word != null) {   // found one
            res.add(p.word);
            p.word = null;     // de-duplicate
        }

        board[i][j] = '#';
        
        if (i > 0) dfs(board, i - 1, j ,p); 
        if (j > 0) dfs(board, i, j - 1, p);
        if (i < board.length - 1) dfs(board, i + 1, j, p); 
        if (j < board[0].length - 1) dfs(board, i, j + 1, p); 
        
        board[i][j] = c;
    }

    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
           }
           p.word = w;
        }
        
        return root;
    }

    class TrieNode {
        String word;
        TrieNode[] next = new TrieNode[26];
    }
}