Word Search

The problem description can be found in LeetCode.

Approach

This is a classic Graph problem. Both BFS and DFS can be applied for this problem. However, usually, the DFS recursive implementation is less verbose and easier to implement.

As soon as we see a matching character, we can start our DFS to all the other characters of the string.

Then, we just need to mark the visited ones. We can either have a visited Set or change the input board. We could also revert the change after the search is complete, since it is a $O(1)$ operation.

Solution

from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # not ideal, but just to avoid to have too many function parameters
        self.board = board
        self.rows, self.cols = len(board), len(board[0])

        for row in range(self.rows):
            for col in range(self.cols):
                if board[row][col] == word[0] and self.dfs(word, row, col):
                    return True

        return False

    def dfs(self, word: str, row: int, col: int) -> bool:
        if not word:
            return True
        if not (0 <= row < self.rows and 0 <= col < self.cols):
            return False
        if self.board[row][col] != word[0]:
            return False

        # mark the current cell as `visited`
        tmp = self.board[row][col]
        self.board[row][col] = ""

        ans = (
            self.dfs(word[1:], row - 1, col)  # up
            or self.dfs(word[1:], row + 1, col)  # down
            or self.dfs(word[1:], row, col - 1)  # left
            or self.dfs(word[1:], row, col + 1)  # right
        )

        # restore original value of the cell
        self.board[row][col] = tmp

        return ans

Complexity

• Time: $O(3^{w}mn)$
• Space: $O(w)$

Where $m$, $n$ and $w$ are the number of rows and columns of the input board and the string word, respectively.