79-WordSearch 单词搜寻

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯法+DFS+状态重置

这个解法涉及到了三个关键词，我们一一来看。

DFS，也就是深度优先搜索算法。和BFS(广度优先搜索算法)的不同我们在此不加论述。
这个算法思路是：把一条路径不断往深里走。已经走过的节点我们会置为True。
这个过程从代码实现角度来看，也就是使用迭代。

如果遇到不符合要求的节点，就需要回溯+状态重置。

回溯就是我们要回到上个节点，检查一下除了这个节点以外，还有没有其他路径，然后对这些路径继续DFS。

当然，我们需要把原先标记为True的节点，重新标记为False。这就是状态重置

有了思路以后，如何代码实现？以下面的代码为例，大体说一下细节。

首先，节点是以二维数组来表示的。那如何标识左右，上下的移动？
这就是上来设置directions的目的。我们用4个cell组成的list来表示不同方向的移动。

其次，如何表示DFS不断向深处遍历的过程？整体思路是迭代。

以__search_word()这个函数为例，这个函数的功能不是确定某一个节点和word的某个字母是否相对应，而是确定以[i,j]开始的某个序列是否和word对应

我们已经查到了word[index]，但是还不能返回True，因为我们还要确定word[index+1]；

由于迭代，我们在确定word[index+1]的过程中还需要确定word[index+2]；

以此类推，这个过程需要进行到word的最后一个字母。如果最后一个字母也能对应上，那么就会返回True，证明从[i, j]开始是可以遍历完word的，从而证明True。

class Solution:
    #          (x-1, y) 
    # (x, y-1) (x,   y)   (x, y+1)
    #          (x+1, y)
    directions = [(0,-1), (-1,0), (0,1), (1,0)] # left up right down

    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)      # row number
        if m == 0:
            return False
        n = len(board[0])   # column number
        # marked: signal whether this point is available.
        # initialization: every point is available. set False.
        marked = [[False for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if self.__search_word(board, word, 0, i, j, m, n, marked):
                    return True
        
        return False


    def __search_word(self, board, word, index, start_x, start_y, m, n, marked):
        # index: word[index]
        # start_x, start_y: beginning point
        # m, n: board's row = m; column = n;
        # marked: signal whether this point is occupied

        if index == len(word)-1:   # `word`'s last letter
            return board[start_x][start_y] == word[index]
        
        if board[start_x][start_y] == word[index]:
            # occupy position before checking word[index+1].
            # if `index+1` is wrong, we have to reset this position `False`.
            marked[start_x][start_y] = True 

            # Start checking word[index+1]
            for direction in self.directions:
                # move to next point.
                new_x = start_x + direction[0]
                new_y = start_y + direction[1]

                # new point isn't occupied & equals word[index+1]
                if 0<= new_x <m and 0<= new_y <n and 
                    not marked[new_x][new_y] and 
                    self.__search_word(board, word, index+1, new_x, new_y, m, n, marked):
                    return True
                
            # word[index+1] cann't be found around start_x & start_y
            # route with (start_x, start_y) is wrong, this pointshould be released.
            marked[start_x][start_y] = False
        return False

上述代码有几处设计的很巧妙的地方。

marked状态初始化。marked是个二维数组，[[False for _ in rang(n)] for _ in range(m)] 这个写法值得学习。
__search_word()这个函数一共使用了两处。调用的格式是self.__search_word(board ... )，首先是要使用self.引导，另外是参数里不要加self。定义函数的时候要加self，但是使用的时候不要加。

这个解法是很直观的。当然，如果用Java或者C++实现的话，效率会更高点。但是解题思路是一致的。

题目描述

回溯法+DFS+状态重置

相关推荐