79. Word Search

Description

The problem is to determine if a given word can be found in a 2D board of characters. You can only move horizontally or vertically from a cell and you cannot revisit the same cell within a single path. The word must be constructed sequentially from the board's characters.

For example, given a board:

[ ['A', 'B', 'C', 'E'],

['S', 'F', 'C', 'S'],

['A', 'D', 'E', 'E'] ]

and a word "ABCCED", the method should return true because the word can be constructed as follows: A -> B -> C -> C -> E -> D.

Intuition

The task is to explore the board to check if the word can be constructed by traversing adjacent cells. The problem can be approached using depth-first search (DFS) with backtracking:

1. Start from each cell in the board.
2. Recursively search for the next character in the word.
3. Mark cells as visited to avoid reusing them in the current path.
4. Backtrack to explore other potential paths if needed.

Approach

1. Initialization: - Check if the board or word is empty. If so, return False. - Initialize a visited matrix to keep track of which cells have been visited.
2. Recursive Function (backtrack): - Base Case: If the index equals the length of the word, return True. - Boundary Check: If the current cell is out of bounds, already visited, or does not match the current character in the word, return False. - Mark as Visited: Mark the current cell as visited. - Explore Directions: Recursively explore all four possible directions (down, up, right, left) from the current cell. - Backtrack: After exploring, unmark the cell to allow other potential paths.
3. Main Search Loop: - Iterate through each cell in the board and start the backtracking process if the cell matches the first character of the word.
4. Return Result: - Return True if the word is found; otherwise, return False.

Complexity

Time Complexity:

O(M * N * 4^L)

• Where M and N are the dimensions of the board, and L is the length of the word.
• In the worst case, each cell is visited multiple times, and there are up to 4^L possible paths to explore due to the four directions.

Space Complexity:

O(M * N)

• Space complexity is determined by the space used for the visited matrix and the recursion stack.
• The visited matrix has a size of M * N, and the maximum depth of recursion is L, which in the worst case can be proportional to the board size.

Code

C++

class Solution {
public:
    bool exist(vector>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        vector> visited(board.size(), vector(board[0].size(), false));
        
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (backtrack(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
private:
    bool backtrack(vector>& board, const string& word, int i, int j, int k, vector>& visited) {
        if (k == word.length()) return true;
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[k]) {
            return false;
        }

        visited[i][j] = true;
        bool found = backtrack(board, word, i + 1, j, k + 1, visited) ||
                     backtrack(board, word, i - 1, j, k + 1, visited) ||
                     backtrack(board, word, i, j + 1, k + 1, visited) ||
                     backtrack(board, word, i, j - 1, k + 1, visited);

        visited[i][j] = false;
        return found;
    }
};

Python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return False
        
        rows, cols = len(board), len(board[0])
        visited = [[False] * cols for _ in range(rows)]
        
        def backtrack(r, c, index):
            if index == len(word):
                return True
            if r < 0 or r >= rows or c < 0 or c >= cols or visited[r][c] or board[r][c] != word[index]:
                return False
            
            visited[r][c] = True
            # Explore all four directions: down, up, right, left
            found = (backtrack(r + 1, c, index + 1) or
                     backtrack(r - 1, c, index + 1) or
                     backtrack(r, c + 1, index + 1) or
                     backtrack(r, c - 1, index + 1))
            
            visited[r][c] = False
            return found
        
        for r in range(rows):
            for c in range(cols):
                if backtrack(r, c, 0):
                    return True
        
        return False

Java

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        
        boolean[][] visited = new boolean[board.length][board[0].length];
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    private boolean backtrack(char[][] board, String word, int i, int j, int k, boolean[][] visited) {
        if (k == word.length()) {
            return true;
        }
        
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(k)) {
            return false;
        }
        
        visited[i][j] = true;
        
        boolean found = backtrack(board, word, i + 1, j, k + 1, visited) ||
                        backtrack(board, word, i - 1, j, k + 1, visited) ||
                        backtrack(board, word, i, j + 1, k + 1, visited) ||
                        backtrack(board, word, i, j - 1, k + 1, visited);
        
        visited[i][j] = false;
        
        return found;
    }
}

JavaScript

var exist = function (board, word) 
{
    const visited = Array.from(Array(board.length), () => Array(board[0].length).fill(false));
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (backtrack(board, word, i, j, 0, visited))
                return true;
        }
    }
    return false;
};

function backtrack(board, word, i, j, k, visited) 
{
    if (k === word.length)
        return true;
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] !== word.charAt(k))
        return false;

    visited[i][j] = true;
    if (backtrack(board, word, i + 1, j, k + 1, visited) ||
        backtrack(board, word, i - 1, j, k + 1, visited) ||
        backtrack(board, word, i, j + 1, k + 1, visited) ||
        backtrack(board, word, i, j - 1, k + 1, visited))
        return true;

    visited[i][j] = false;
    return false;
}