Word Search

Matrix
Medium

Approach

Diagrams

Analysis

Time

O(n * 3^l)

Space

O(l)
class Solution:
    def exist(self, board, word):
        if not board:
            return False

        self.numRows = len(board)
        self.numCols = len(board[0])
        self.board = board

        for row in range(self.numRows):
            for col in range(self.numCols):
                if self.dfs(row, col, word):
                    return True

        return False

    def dfs(self, row, col, suffix):
        wordIsFound = len(suffix) == 0

        if wordIsFound:
            return True

        isValid = 0 <= row < self.numRows and 0 <= col < self.numCols
        isBeingVisited = suffix[0] != self.board[row][col] if isValid else False

        if not isValid or isBeingVisited:
            return False

        curLetter = self.board[row][col]
        self.board[row][col] = '#'

        rowOffsets = [-1, 0, 1, 0]
        colOffsets = [0, 1, 0, -1]

        for offset in range(len(rowOffsets)):
            nextRow = row + rowOffsets[offset]
            nextCol = col + colOffsets[offset]

            if self.dfs(nextRow, nextCol, suffix[1:]):
                return True

        self.board[row][col] = curLetter

        return False

Learn

#Backtracking

Videos