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();
        root.cnt = -1;
        for (String word : words) root.insert(word);
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                StringBuilder sb = new StringBuilder();
                backtrack(y, x, root, sb, res);
            }
        }
        return res;
    }

    private void backtrack(int y, int x, TrieNode curr, StringBuilder sb, LinkedList<String> res) {
        if (curr == null || curr.cnt == 0) return;
        if (curr.isKey) {
            res.add(sb.toString());
            root.remove(sb.toString());
        }
        char c;
        if (y < 0 || n <= y || x < 0 || m <= x || (c = board[y][x]) == '#') return;
        sb.append(c);
        board[y][x] = '#';
        curr = curr.next[(int) c - 'a'];
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            backtrack(ny, nx, curr, sb, res);
        }
        sb.deleteCharAt(sb.length() - 1);
        board[y][x] = c;
    }

    class TrieNode {
        int cnt;
        boolean isKey;
        TrieNode[] next = new TrieNode[26];

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

        void remove(String str) {
            TrieNode curr = this;
            for (char c : str.toCharArray()) {
                int i = (int) c - 'a';
                curr = curr.next[i];
                curr.cnt--;
            }
            curr.isKey = false;
        }
    }
}