在这里插入图片描述
思路
每次以当前位置为初始位置开始遍历,看是否找到单词
(以官方题解做出)
v:代表等于work[k]且已走过的位置

d:四个方向

回溯(遍历):

匹配不上:终止

找到了:终止(先判断匹配再判断找到)

未终止,继续循环:记录当前已走过位置(等于work[k]),以当前位置向四周遍历,找到则往对应方向继续循环;四个方向都找不到匹配,则回退再继续遍历

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        """
        回溯三部曲:满足结果、匹配不上、继续搜索
        """
        #方向
        d=[(0,1),(0,-1),(1,0),(-1,0)]
        #已经走过的位置
        v = set()
        
        def backtrack(i,j,k):
            #匹配不上
            if board[i][j]!=word[k]:
                return False
            #满足结果
            if k==len(word)-1:
                return True
            #当前字符满足,继续往下搜 ,先标记已经走过的位置   走过的位置不能再走
            v.add((i,j))
            r = False
            #当前位置往四个方向继续搜索
            for s1,s2 in d:
                s,t=s1+i,s2+j
                if (s>=0 and s<len(board)) and (t>=0 and t<len(board[0])) and (s,t) not in v:
                    if backtrack(s,t,k+1):
                        return True
            #四个方向都找不到,回退
            v.remove((i,j))
        for i in range(len(board)):
            for j in range(len(board[0])):
                #每次以当前位置为起点开始遍历,查看是否找到
                if backtrack(i,j,0):
                    return True
        return False

超限(更容易理解):

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        """
        回溯三部曲:满足结果、匹配不上、继续搜索
        """
        #方向
        # d=[(0,1),(0,-1),(1,0),(-1,0)]
        
        def backtrack(i,j,k):
            #满足结果
            if board[i][j]==word[k] and k==len(word)-1:
                return True
            #匹配不上
            if board[i][j]!=word[k]:
                return False
            #当前字符满足,继续往下搜
            #先标记已经走过的位置   走过的位置不能再走
            temp=board[i][j]
            board[i][j]=1
            #超限
            # for s1,s2 in d:
            #     s,t=s1+i,s2+j
            #     if (s>=0 and s<len(board)) and (t>=0 and t<len(board[0])) and backtrack(s,t,k+1):
            #         return True
            if i-1>=0 and k+1<len(word) and backtrack(i-1,j,k+1):
                return True
            if j-1>=0 and k+1<len(word) and backtrack(i,j-1,k+1):
                return True
            if i+1<len(board) and k+1<len(word) and backtrack(i+1,j,k+1):
                return True
            if j+1<len(board[0]) and k+1<len(word) and backtrack(i,j+1,k+1):
                return True
            #四个方向都找不到,还原
            board[i][j]=temp
        for i in range(len(board)):
            for j in range(len(board[0])):
                #每次以当前位置为起点开始遍历,查看是否找到
                if backtrack(i,j,0):
                    return True
        return False

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部