79. Word Search

Published on June 19, 2023

Question

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

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

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Algorithm

A typical backtracking problem, (or so called flood fill), we traverse all the elements in the board and start from each of those element to check if we can get a valid string.

The helper(char[][] board, int i, int j, String word, int index) helps us to do a DFS to check if starts from board[i][j], can we find the the string word.substring(i, word.length()-1).

Code

class Solution {
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (helper(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean helper(char[][] board, int i, int j, String word, int index) {
        int m = board.length;
        int n = board[0].length;
        if (board[i][j] == word.charAt(index)) {
            if (index == word.length() - 1) {
                return true;
            } else {
                visited[i][j] = true;
                if (i-1 >= 0 && !visited[i-1][j]) {
                    if (helper(board, i-1, j, word, index+1)) {
                        return true;
                    }
                }
                if (i+1 < m && !visited[i+1][j]) {
                    if (helper(board, i+1, j, word, index+1)) {
                        return true;
                    }
                }
                if (j-1 >= 0 && !visited[i][j-1]) {
                   if (helper(board, i, j-1, word, index+1)) {
                       return true;
                   }
                }
                if (j+1 < n && !visited[i][j+1]) {
                    if (helper(board, i, j+1, word, index+1)) {
                        return true;
                    }
                }
                visited[i][j] = false;
            }
        }
        return false;
    }
}