Word Search

Question

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.

Example

Given board =

[
  "ABCE",
  "SFCS",
  "ADEE"
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

Tags

Backtracking Facebook Depth First Search

Analysis

基本思路比较简单：从board上每一个点出发，用depth first search （DFS）上下左右四方向搜索匹配的word。需要注意到几点： 1. 考虑board的边界 2. cell是否已经被遍历过（临时转换为特定标识字符，比如'#'，recursion返回后再重置回原来的值，这样可以省去额外开辟二维数组visited[i][j]的空间复杂度) 3. 搜索结束的标志是k == word.length()

Note:

标记元素是否被访问过，最直接的办法可以用一个额外的二维数组visited[][]

而临时转换为特定标识字符，比如'#'，recursion返回后再重置回原来的值，则可节省额外空间。

此外LeetCode讨论区提到一种可以节约额外空间的方法：

board[i][j] ^= 256;

就是利用ASCII character是0~127之间， 与256异或（二进制每位都取反）之后得到的>=128, 所以一定不会重复，recursion返回之后用同样的语句即可将元素转化为原始值：

board[i][j] ^= 256;

但是个人感觉这个运算虽然利用了board中数组元素的特性，但是并不够通用，其实只要掌握了类似标记访问的思路，比如'#', 就可以作为通行解决办法。

Solution

DFS - with additional space for visited[][] matrix (12ms 52.97% AC)

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        if (word.length() == 0) {
            return true;
        }
        int M = board.length;
        int N = board[0].length;
        boolean[][] visited=new boolean[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (existHelper(board, visited, i, j, word, 0)) return true;
            }
        }
        return false;
    }
    private boolean existHelper(char[][] board, boolean[][] visited, int row, int col, String word, int index) {
        if (index == word.length()) return true;
        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) return false;
        if (word.charAt(index) != board[row][col] || visited[row][col]) return false;

        visited[row][col] = true;
        int[] dx = new int[] {0, 1, 0, -1};
        int[] dy = new int[] {1, 0, -1, 0};

        for (int i = 0; i < dx.length; i++) {
            if ( existHelper(board, visited, row + dx[i], col + dy[i], word, index + 1)) {
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }

}

DFS - using temporary '#' mark visited element (15 ms 36.92% AC)

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        if (word.length() == 0) {
            return true;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    boolean result = dfs(board, word, i, j, 0);
                    if (result) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int k) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        if (word.length() == 0) {
            return true;
        }

        if (word.length() == k) {
            return true;
        }

        boolean result = false;
        if (insideBoard(board, i, j) && board[i][j] == word.charAt(k)) {
            char temp = board[i][j];
            board[i][j] = '#';
            result = dfs(board, word, i + 1, j, k + 1) ||
                dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) ||
                dfs(board, word, i, j - 1, k + 1);
            board[i][j] = temp;
        }
        return result;
    }

    private boolean insideBoard(char[][] board, int i, int j) {
        return (i >= 0 && i < board.length && j >= 0 && j < board[0].length);
    }
}

Reference

PreviousNumber of Distinct IslandsNextCourse Schedule

Last updated