Word Search

Problem

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.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution

Backtracking Solution:

public class Solution {

    public boolean exist(char[][] board, String word) {
        if (board == null || word == null || board.length == 0 || word.length() == 0) return false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (find(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }

    private boolean find(char[][] board, int i, int j, String word, int index) {
        if (index == word.length()) return true;
        if (i < 0 || j < 0 || i == board.length || j == board[0].length || board[i][j] != word.charAt(index)) return false;
        board[i][j] = '*';
        boolean res = find(board, i + 1, j, word, index + 1) || find(board, i, j + 1, word, index + 1) || find(board, i - 1, j, word, index + 1) || find(board, i, j - 1, word, index + 1);
        board[i][j] = word.charAt(index); //This line executes only if board[i][j] == word.charAt(index)
        return res;
    }
}

Analysis

The idea of this solution is that we recursively check adjacent elements in the board
In the recursive find() method, we only return true if index == word.length()
We will directly return false if word.charAt(index) != board[i][j]
To avoid ArrayIndexOutofBorderException, we check the validation of index i and index j
Then we know that we find the character at current index from board
To avoid duplicated used, we mark it as board[i][j] == '*'
After that, we recursively check adjacent elements with next index and store the res
Before return res, we need to set board[i][j] = word.charAt(index) back

Complexity Analysis:

• Time: O(m n 4 ^ k), where m = board.length, n = board[0].length, k = word.length()
• Space: O(k), the method will be called on stack at maximum with word.length() times