Python dfs solution with comments.


  • 37
    C
    def exist(self, board, word):
        if not board:
            return False
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if self.dfs(board, i, j, word):
                    return True
        return False
    
    # check whether can find word, start at (i,j) position    
    def dfs(self, board, i, j, word):
        if len(word) == 0: # all the characters are checked
            return True
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:
            return False
        tmp = board[i][j]  # first character is found, check the remaining part
        board[i][j] = "#"  # avoid visit agian 
        # check whether can find "word" along one direction
        res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
        or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
        board[i][j] = tmp
        return res

  • 0
    W

    is it correct?

    board[i][j] = "#" # avoid visit agian

    str is immutable, I think we could not replace a character. can we? or I may be wrong.


  • 1
    C

    Here board is a two dimensional array ,not a list of string~


  • 0
    W

    Oh... yes, you're right! thanks


  • 0
    C

    Yes,but we did not change characters inside the string,we replace the string (reassignment),so it works.


  • -1
    T

    Similar idea with inner function:

    def exist(self, board, word):
            L= len(word)
            # if not L: return True
            M = len(board)
            # if not M: return False
            N = len(board[0])
            def DFS(i, j, l):
                if board[i][j] != word[l]: return False
                if l+1 == L: return True
                board[i][j] += '@'
                hasFound = (i-1>=0 and DFS(i-1, j, l+1)) or (i+1 < M and DFS(i+1, j, l+1)) or\
                    (j-1 >= 0 and DFS(i, j-1, l+1)) or (j+1 < N and DFS(i, j+1, l+1))
                board[i][j] = board[i][j][0] #backtrace
                return hasFound
            
            for i in range(M):
                for j in range(N):
                    if DFS(i,j, 0):
                        return True
            return False

  • 0
    R
    This post is deleted!

  • 0
    G

    @caikehe Excellent idea ! I want to know the time complexity of DFS ,thank you !~


  • 0
    A

    without modifying the original board, using a stack to track the path:

    class Solution(object):
        def exist(self, board, word):
            
            self.word = word
            self.found = False
            for row in range(len(board)):
                for col in range(len(board[0])):
                    self.visited = []
                    self.visitedSet = set()
                    self.dfs(board,row,col,0)
                    if self.found:
                        return True
            return False
    
        
        def dfs(self,board,row,col,i):
    
            if i == len(self.word):
                self.found = True
    
            if not self.found and row >= 0 and col >= 0 and row<len(board) and col<len(board[0]) and board[row][col] == self.word[i] and (row,col) not in self.visitedSet:
                self.visited += [(row,col)]
                self.visitedSet.add((row,col))
                self.dfs(board,row+1,col,i+1)
                self.dfs(board,row-1,col,i+1)
                self.dfs(board,row,col+1,i+1)
                self.dfs(board,row,col-1,i+1)
            
                if not self.found:
                    self.visitedSet.remove(self.visited.pop())
    

  • 0
    A

    @axelramar9

    Using a list as stack is enough, no need to use a set:

    class Solution(object):
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            if not board:
                return False
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if self.dfs(board, i, j, word, []):
                        return True
            return False
    
        # check whether can find word, start at (i,j) position    
        def dfs(self, board, i, j, word, visited):
            if len(word) == 0: # all the characters are checked
                return True
            if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j] or (i, j) in visited:
                return False
            visited.append((i, j))
            res = self.dfs(board, i-1, j, word[1:], visited) or self.dfs(board, i+1, j, word[1:], visited) \
            or self.dfs(board, i, j-1, word[1:], visited) or self.dfs(board, i, j+1, word[1:], visited)
            if not res:
                a = visited.pop()
            return res

  • 0
    S

    @WeiFoo yeah, I think that's why we do board[i][j] = tmp for other runs of recursion


  • 0
    A

    @ahoosh a list as a stack is enough, but a set will address the elements in constant time.

    Probably (asking all the experts here) a better implementation would be by using OrderedSet.


Log in to reply
 

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