import java.util.LinkedList;

class Solution {
    private int[] dy = new int[]{0, 1, 0, -1};
    private int[] dx = new int[]{1, 0, -1, 0};

    private char[][] board;
    private int n;
    private int m;
    private TrieNode root;

    public List<String> findWords(char[][] board, String[] words) {
        LinkedList<String> res = new LinkedList<>();
        if ((n = board.length) == 0 || (m = board[0].length) == 0 || words.length == 0) return res;
        this.board = board;
        root = new TrieNode();
        for (String word : words) root.insert(word);
        for (int y = 0; y < n; y++)
            for (int x = 0; x < m; x++)
                backtracking(y, x, root, res);
        return res;
    }

    private void backtracking(int y, int x, TrieNode curr, LinkedList<String> res) {
        if (curr == null) return;
        if (curr.word != null) {
            res.add(curr.word);
            curr.word = null;
        }
        char c;
        if (y < 0 || n <= y || x < 0 || m <= x || (c = board[y][x]) == '#') return;
        board[y][x] = '#';
        curr = curr.next[c - 'a'];
        for (int i = 0; i < 4; i++) backtracking(y + dy[i], x + dx[i], curr, res);
        board[y][x] = c;
    }

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

        void insert(String str) {
            TrieNode curr = this;
            for (char c : str.toCharArray()) {
                int i = c - 'a';
                if (curr.next[i] == null) curr.next[i] = new TrieNode();
                curr = curr.next[i];
            }
            curr.word = str;
        }
    }
}