LC212_BADSOL

// LC 212 FAILED SOLUTION (34/37)
// https://leetcode.com/problems/word-search-ii/description/

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<String>();
        if (board.length == 0 || board[0].length == 0) {
            return ans;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                for (String w : words) {
                    if (board[i][j] == w.charAt(0) &&
                        BT(board, new int[] {i, j}, w, new boolean[board.length][board[0].length]) &&
                        !ans.contains(w)) {
                        ans.add (w);
                    }
                }
            }
        }
        return ans;
    }
    public boolean BT(char[][] board, int[] pos, String word, boolean[][] visited) {
        if (board[pos[0]][pos[1]] != word.charAt(0)) {
            return false;
        }
        else if (word.length() == 1) {
            return true;
        }
        visited[pos[0]][pos[1]] = true;
        int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : dirs) {
            int x = dir[0] + pos[0];
            int y = dir[1] + pos[1];
            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && !visited[x][y]) {
                if (BT(board, new int[] {x, y}, word.substring(1), visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}