leetcode hot 100 单词搜索

79. 单词搜索
已解答
中等
相干标签
相干企业
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母次序，通过相邻的单位格内的字母构成，此中“相邻”单位格是那些程度相邻或垂直相邻的单位格。同一个单位格内的字母不答应被重复使用。

import copy
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        # o（mnkk）的就是遍历一遍找到开头，对所有开头左dfs
        m = len(board)
        n = len(board[0])
        visted = copy.deepcopy(board)
        self.ret = False

 
        def dfs(x,y,count):
            if count==len(word)-1 :
                self.ret = True
                return
            tmp = False
            count+=1
            if x>=0 and x<m-1 and y>=0 and y<n and board[x+1][y]==word[count] and visted[x+1][y]==0:
               
                visted[x+1][y]=1
                tmp1 = dfs(x+1,y,count)
                tmp = tmp or tmp1
                visted[x+1][y]=0
            if x>=1 and x<m and y>=0 and y<n and board[x-1][y]==word[count] and visted[x-1][y]==0:
                visted[x-1][y]=1
                tmp2 = dfs(x-1,y,count)
                tmp = tmp or tmp2
                visted[x-1][y]=0
            if x>=0 and x<m and y>=0 and y<n-1 and board[x][y+1]==word[count]  and visted[x][y+1]==0:
                visted[x][y+1]=1
                tmp3 = dfs(x,y+1,count)
                tmp = tmp or tmp3
                visted[x][y+1]=0
            if x>=0 and x<m and y>=1 and y<n and board[x][y-1]==word[count] and visted[x][y-1]==0:
                visted[x][y-1]=1
                tmp4 = dfs(x,y-1,count)
                tmp = tmp or tmp4
                visted[x][y-1]=0
            return tmp
           

       
        for i in range(m):
            for j in range(n):
                visted[j]=0

 
        for i in range(m):
            for j in range(n):
                if board[j]==word[0]:
                    visted[j]=1
                    dfs(i,j,0)
                        # return True
                    visted[j]=0  
               


 
        # count=0

        # while self.queue!=[]:
        #     if count==len(word)-1 and self.queue!=[]:
        #         return True
        #     size = len(self.queue)
        #     count+=1
        #     for i in range(size):
        #         tmp = self.queue[0]
        #         del self.queue[0]
        #         x=tmp[0]
        #         y=tmp[1]
        #         if x>=0 and x<m-1 and y>=0 and y<n and board[x+1][y]==word[count] and visted[x+1][y]==0:
        #             self.queue.append([x+1,y])
        #             visted[x+1][y]=1
        #         if x>=1 and x<m and y>=0 and y<n and board[x-1][y]==word[count] and visted[x-1][y]==0:
        #             self.queue.append([x-1,y])
        #             visted[x-1][y]=1
        #         if x>=0 and x<m and y>=0 and y<n-1 and board[x][y+1]==word[count]  and visted[x][y+1]==0:
        #             self.queue.append([x,y+1])
        #             visted[x][y+1]=1
        #         if x>=0 and x<m and y>=1 and y<n and board[x][y-1]==word[count] and visted[x][y-1]==0:
        #             self.queue.append([x,y-1])
        #             visted[x][y-1]=1

           
        return self.ret

 
               


 
       
这里我们的结构是使用dfs回溯遍历，因为每次开始之后遍历完之后visted需要变回原样


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。