Accepted Python backtracking solution


  • 1
    X
    class Solution:
        # @param board, a list of lists of 1 length string
        # @param word, a string
        # @return a boolean
        def exist(self, board, word):
        #backtracking, recursion, dfs
            def search(board, word, row, col):
                if word == "":
                    return True
                original = board[row][col]
                board[row][col] = "."
                for i in [row-1, row+1]:
                    if i < len(board) and i > -1:
                        if board[i][col] != "." and board[i][col] == word[0]:
                            if search(board, word[1:], i, col):
                                return True
                for j in [col-1, col+1]:
                    if j < len(board[0]) and j > -1:
                        if board[row][j] != "." and board[row][j] == word[0]:
                            if search(board, word[1:], row, j):
                                return True
                board[row][col] = original
                return False
            
            for row in range(len(board)):
                for col in range(len(board[0])):
                    if board[row][col] == word[0]:
                        if search(board, word[1:], row, col):
                            return True
            return False

  • 0
    C

    The original board's content will be changed when there is True returned...


Log in to reply
 

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