欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

79. Word Search

程序员文章站 2022-07-14 17:30:27
...
Depth first search , recursion

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        visited=[[False for j in xrange(len(board[0]))]for i in xrange(len(board))]
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if self.recursion(board,word,visited,0,i,j):
                    return True 
        return False 
        
    def recursion(self,board,word,visited,cur,i,j):
        if cur==len(word): return True 
        
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or visited[i][j] or board[i][j]!=word[cur]:
            return False
        visited[i][j]=True
        
        result=self.recursion(board,word,visited,cur+1,i+1,j) or \
                self.recursion(board,word,visited,cur+1,i-1,j) or \
                self.recursion(board,word,visited,cur+1,i,j+1) or\
                self.recursion(board,word,visited,cur+1,i,j-1) 
        visited[i][j]=False
        
        return result
         

转载于:https://www.jianshu.com/p/f400c720c0a5