Python, Backtracking, DFS easy to read solution. Includes complexity explanation


  • 0
    S
    class Solution(object):
        def dfs(self, board, word, x, y, start):
            if start == len(word):
                return False
            if board[x][y] != word[start] or board[x][y] == -1:
                return False
            if start == len(word) - 1:
                return True
                
            # mark visited, otherwise you can loop the characters
            tmp = board[x][y]
            board[x][y] = -1
            for i in range(4):
                xx = x + self.x_dirs[i]
                yy = y + self.y_dirs[i]
                if 0 <= xx < self.w and 0 <= yy < self.h:
                    if self.dfs(board, word, xx, yy, start + 1):
                        return True
            board[x][y] = tmp
            return False
    
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            if not board:
                return False
    
            self.x_dirs = [-1, 0, 1, 0]
            self.y_dirs = [0, 1, 0, -1]
            self.w = len(board)
            self.h = len(board[0])
            
            for x in range(self.w):
                for y in range(self.h):
                    if self.dfs(board, word, x, y, 0):
                        return True
            return False
    

    The time complexity of this algorithm is O(nm^2) where n and m are the height and widths of the board. There is a square because per element in the board we are doing a search that can be 4^(length_of_word) where 4^(length_of_word) == m*n in the worst case. (The 4 is there because we go in 4 directions recursively per character in the word)

    The average case time complexity would be O(n * m * 4^(length_of_word).

    The space complexity is constant because instead of a visited map we do in-place board mutations :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.