79. Word Search (backtracking)

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

avoid using a boolean array to store used, just set " board[i][j] = ' ' "

visited = new boolean[board.length][board[0].length];

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0 ; i < board.length; i++) {
            for (int j = 0; j < board[i].length;j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
                    return true; // if find first char, and dfs search ok
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board,int i, int j, int count, String word) {
        if (count == word.length()) { // length equals to ori word, good!
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length 
            || board[i][j] != word.charAt(count)) {
            return false; // outboud
        }
        
        char temp = board[i][j]; // backtracking
        board[i][j] = ' '; // set to empty to represent used
        // use or, so can't use dirs[]
        boolean result = 
            dfs(board, i + 1, j, count+1, word) ||
            dfs(board, i - 1, j, count+1, word) ||
            dfs(board, i, j + 1, count+1, word) ||
            dfs(board, i, j - 1, count+1, word);
        board[i][j] = temp; // add back
        return result;
    }
}

with pruning

class Solution {
    private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
    public boolean exist(char[][] grid, String word) {
        
        if (!pruning(grid, word)) {
            return false;
        }
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == word.charAt(0) && dfs(grid, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean pruning(char[][] grid, String word) {
        int m = grid.length;
        int n = grid[0].length;
        
        // pruning: case 1: not enough characters in board
        if (word.length() > m * n) {
            return false;
        }
        
        // pruning: case 2: board does not contain characters or enough characters that word contains
        Map<Character, Integer> count = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int temp = count.getOrDefault(grid[i][j], 0);
                count.put(grid[i][j], temp + 1);
            }
        }
        
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!count.containsKey(c)) {
                return false; // cant find word's char in hashmap
            } else { // remove count one by one, because word maybe duplicate
                int temp = count.get(c);
                if (temp == 1) {
                    count.remove(c);
                } else {
                    count.put(c, temp - 1);
                }
            }
        }
        return true;
    }
    
    private boolean dfs(char[][] grid, String word, int start, int i, int j) {
        if (start == word.length()) {
            return true;
        }
        if (!isValid(grid, i, j) || word.charAt(start) != grid[i][j]) {
            return false;
        }
        
        char temp = grid[i][j];
        grid[i][j] = ' ';
        
        boolean result = false;
        for (int[] dir : DIRS) {
            result = dfs(grid, word, start + 1, i + dir[0], j + dir[1]);
            if (result) { // find 就 break
                break;
            }
        } 
        
        grid[i][j] = temp;
        return result;
    }
    private boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 & j < grid[0].length;
    }
}

/*
dfs search

how to ?

put first word in dfs search, then 4 direction

dfs() {
 if (start == word.length()) {
    return true;
 }
 
 if (4 direction) {
    get result
    if (not ok return false)
 }
 return result
}
*/

new version, this is more intutive

use visited

class Solution {
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, 0, i, j, new boolean[m][n])) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int start, int i, int j, boolean[][] visited) {
        if (start == word.length()) {
            return true;
        }
        if (!inArea(board, i, j) || visited[i][j] || word.charAt(start) != board[i][j]) {
            return false;
        }

        visited[i][j] = true; 
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (dfs(board, word, start+1, x, y, visited)) {
                return true;
            }
        }
        visited[i][j] = false; 
        return false;
    }
    private boolean inArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >=0 && y < board[0].length;
    }
}
/*
needs match word[0] to start

for (board)

if (ij == word[0]) {
    dfs(start, i, j, )
}
retur

start == word.length
*/

not use visited

以後還是寫在外面好了

class Solution {
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, 0, i, j)) {
                    return true; // 為什麼都找到第一個字了, 還要傳 index 0 進去？
                } // 因為 mark 是在 dfs 裡面做的, backtracking 也是
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int start, int i, int j) {
        if (start == word.length()) {
            return true;
        }
        if (!inArea(board, i, j) || word.charAt(start) != board[i][j]) {
            return false;
        }
        char temp = board[i][j];
        board[i][j] = ' '; 
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (dfs(board, word, start+1, x, y)) {
                return true;
            }
        }
        board[i][j] = temp; 
        return false;
    }
    private boolean inArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >=0 && y < board[0].length;
    }
}