Word Search

Intuition

We could use DFS to search for the correct answer. While doing the DFS process, once we have used a letter, we need to mark it to None to not use it for more than once.

Solution


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board or not board[0]:
            return word == ''

        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if self._dfs(board, i, j, 0, word):
                    return True
        return False

    def _dfs(self, board, i, j, index, word):
        m, n = len(board), len(board[0])
        c = word[index]
        if board[i][j] != word[index]:
            return False
        elif index + 1 == len(word):
            return True
        board[i][j] = None

        for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if not 0 <= x < m or not 0 <= y < n:
                continue
            if self._dfs(board, x, y, index + 1, word):
                return True

        board[i][j] = c