BFS中的Leetcode 79字搜索问题

Question

我遇到了一个使用Python解决Leetcode79字搜索的问题。

给定一个m×n的字符板网格和一个字符串字，如果该网格中存在字，则返回true。

该字可以由顺序相邻单元格的字母构成，其中相邻单元格水平或垂直相邻。同一个字母单元格不能使用不止一次。

我试图使用一个字符队列和一个BFS来查看是否有一个单词存在于黑板上，但解决方案似乎对某些单词有效，而不是其他单词。例如，在第一个testcase中，访问的顺序似乎是[[0,0]，[0,1]，[0,2]，[1,2]，[0,3]]而不是预期的[[0,0]，[0,1]，[0,2]，[1,2]，[2,2]，[2,1]]。我不确定我是否忽略了一些错误（除了从一个起点进行测试之外，我希望在修复这个问题后修复它）。

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """

        rows,cols=len(board),len(board[0])
        directions=[[1,0],[-1,0],[0,1],[0,-1]]
        word=str(word)
        mq=list(word)
        
        visited=[]
        startlist=[]
        
        #find all start points
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]==mq[0]:
                    if [i,j] not in startlist:
                        startlist.append([i,j])
                        
        def bfs(r,c):
            q=collections.deque()
            q.append([r,c])
            visited.append([r,c])   
            if board[r][c]==mq[0]:
                mq.pop(0) 
            while q:
                x,y=q.popleft()
                for dx,dy in directions:
                    row,col=x+dx,y+dy
                    if row in range(rows):
                        if col in range(cols):
                            if mq:
                                if board[row][col]==mq[0]:
                                    if [row,col] not in visited:
                                        mq.pop(0)
                                        visited.append([row,col])
                                        q.append([row,col])
                                    

        x,y=startlist[0]
        bfs(x,y)
        
        if not mq:
            return True
        else:
            return False
                        
                        ````

Answer 1

您正在尝试的算法有几个问题：

• visited应该只收集当前路径上的节点。其他路径限制当前路径的自由是不对的。
• mq.pop(0)将永远删除该字符，但是当您在不同的方向上循环时，所有这些迭代都应该与相同的mq字符进行比较...所以这是不对的。相反，您应该跟踪mq中的索引以便与之进行比较。这可以与队列中的行和列一起存储（作为第三个信息）。
• BFS仅在startlist中的第一个单元格启动。startlist中的所有其他元素都可以有很好的开始位置，但从未尝试过。

使用DFS而不是BFS将更容易实现（并且使用更少的内存）。