Problem of The Day: Word Search

Problem Statement

Intuition

Looking at the problem, my first thought is to traverse the board and check if we can form the given word by moving in all possible directions from each cell.

Approach

To solve the problem, I’ll use backtracking. Starting from each cell in the board, I’ll explore all possible paths to form the given word. If at any point we find that the current path matches the word, we return True. If we explore all possible paths from a cell and none of them match the word, we backtrack and explore other paths.

Complexity

• Time complexity: O(NM4^L) where N and M are the dimensions of the board and L is the length of the word. We traverse through each cell of the board and for each cell, we explore up to 4 directions (up, down, left, right), and the maximum length of the word can be L.

• Space complexity: O(L) where L is the length of the word. The space complexity is primarily due to the recursion stack used in backtracking.

Code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS = len(board)
        COLS = len(board[0])

        def backtrack(row, col, word_idx):
            if word_idx == len(word):
                return True
            temp = board[row][col]
            board[row][col] = '#'
            for x, y in [(-1,0),(1,0),(0,1),(0,-1)]:
                r, c = row + x, col + y
                if 0 <= r < ROWS and 0 <= c < COLS and board[r][c] != '#' and word[word_idx] == board[r][c]:
                    if backtrack(r, c, word_idx + 1):
                        return True
            board[row][col] = temp
            return False

        for row in range(ROWS):
            for col in range(COLS):
                if board[row][col] == word[0] and backtrack(row, col, 1):
                    return True
        return False