Word Search

1package pkg5leetcode.blind75;2 3/*4 * Word Search | LC 795 * APPROACH: DFS backtracking from each cell with visited marking.6 * COMPLEXITY: Time O(mn * 4^L), Space O(L)7 */8public class blind75_LC79WordSearch {9    static boolean exist(char[][] board, String word) {10        for (int i = 0; i < board.length; i++)11            for (int j = 0; j < board[0].length; j++)12                if (dfs(board, word, i, j, 0)) return true;13        return false;14    }15 16    static boolean dfs(char[][] b, String w, int r, int c, int idx) {17        if (idx == w.length()) return true;18        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(idx)) return false;19        char tmp = b[r][c];20        b[r][c] = '#';21        boolean found = dfs(b, w, r + 1, c, idx + 1) || dfs(b, w, r - 1, c, idx + 1)22                || dfs(b, w, r, c + 1, idx + 1) || dfs(b, w, r, c - 1, idx + 1);23        b[r][c] = tmp;24        return found;25    }26 27    public static void main(String[] args) {28        check(exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}, "ABCCED"), "case1");29        check(!exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}, "ABCB"), "case2");30        System.out.println("all tests passed");31    }32 33    static void check(boolean cond, String name) {34        if (!cond) throw new AssertionError("FAILED: " + name);35        System.out.println("  PASS " + name);36    }37}