Python simple dfs solution


  • 12
    S
    def exist(self, board, word):
        if not word:
            return True
        if not board:
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.exist_helper(board, word, i, j):
                    return True
        return False
                        
    def exist_helper(self, board, word, i, j):
        if board[i][j] == word[0]:
            if not word[1:]:
                return True
            board[i][j] = " " # indicate used cell
            # check all adjacent cells
            if i > 0 and self.exist_helper(board, word[1:], i-1, j):
                return True
            if i < len(board)-1 and self.exist_helper(board, word[1:], i+1, j):
                return True
            if j > 0 and self.exist_helper(board, word[1:], i, j-1):
                return True
            if j < len(board[0])-1 and self.exist_helper(board, word[1:], i, j+1):
                return True
            board[i][j] = word[0] # update the cell to its original value
            return False
        else:
            return False

  • 0
    D

    what would be time complexity for this algorithm? exist has loop of O(rows * cols) and exist_helper, checks like DFS which seems like len of word. But in all 4 direction.


  • 0
    F

    @dharaB

    Should it be O(mn4^len(word))?


  • 0
    R
    This post is deleted!

  • 0
    W
    This post is deleted!

  • 0
    D

    The above code is quite good but some cases add a bit of confusion.
    Like:

    if not word[1:]:
      return True
    

    and extra else at the end.

    The code can be simplified to:

    def search_word_util(self, board, row, col, word):
            if len(word) == 0:
                return True
            
            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[0]:
                return False
            
            board[row][col] = " "
    
            if self.search_word_util(board, row-1, col, word[1:]):
                return True
            if self.search_word_util(board, row+1, col, word[1:]):
                return True
            if self.search_word_util(board, row, col-1, word[1:]):
                return True
            if self.search_word_util(board, row, col+1, word[1:]):
                return True
            
            board[row][col] = word[0]
            return False
    

    It handles all the cases for which extra conditions were added in the above code.


Log in to reply
 

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