基本信息

  • 题号：79
  • 题厂：脸书
  • 难度系数：中


在 m * n 的矩阵中，查找单词。找到返回 true，没找到返回 false。

查找方向可以上、下、左、右 四个方向查找。

解题思路

  • 按照遍历矩阵常规思路，当坐标字符和目标搜寻单词第一个字符匹配时，开启上、下、左、右 四个方向查找模式。
  • 如果满足搜索条件，提前返回 true 结束循环。
  • 如果矩阵遍历完都没有返回值，则该单词没能在矩阵中找到，末尾返回 false。
  • 为了让代码简洁，把搜寻单词代码单独写成一个 recessive 方法。
  • 对单词进行上、下、左、右 四个方向查找时，需要用到 backtracking 思想。例如本题当中我们创建一个叫 path 的 set 变量，每找到一个字符就往 path 添加记录；搜寻完了之后，再退后一步回归上一个状态以供下一次查找……
   # 添加坐标供记录
   path.add((r, c))           
   ‘’‘
   ……
   要遍历的代码
   ……
   ‘’‘
   # backtrack 返回上一个状态……          
   path.remove((r, c))



class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        row, col = len(board), len(board[0])
       
        path = set()
        def searchWord(r, c, i):
            if i == len(word):
                return True
            
            if (
                r < 0
                or r >= row
                or c < 0
                or c >= col
                or (r, c) in path
                or board[r][c] != word[i]
            ):
                return False
            
            path.add((r, c))
            
            res = (
                searchWord(r + 1, c, i + 1)
                or searchWord(r - 1, c, i + 1)
                or searchWord(r, c + 1, i + 1)
                or searchWord(r, c - 1, i + 1)
            )
            
            path.remove((r, c))
            
            return res
        
        for r in range(row):
            for c in range(col):
                if board[r][c] == word[0]:
                    if searchWord(r, c, 0):
                        return True
                    
        return False


Constraints

本题涉及 backtracking，recursion，还有 bfs dfs 等问题，constraints 不再特别重点。考试解题前，还是可以向考官询问确认一下各种变量的取值范围。


Big O

  • Time：O（n * m * 4 * k ），n 和 m 分别代表矩阵长宽，k 代表目标单词长度。最坏的情况下，我们遍历了矩阵所有坐标，每到一个坐标又要进行一次长度等于 word length 的深度 + 4 个方向的广度查询……
  • space：O（k），引用了 path set，k 为目标搜寻单词长度。

本题思路较复杂，如有错误，欢迎大佬评论区指证。


测试

  • 单词存在矩阵案例
  • 单词不存在矩阵案例
  • 单词在矩阵中可以通过 2 + 路径查找案例……
  • ……


总结

在矩阵数据结构中查找 XXX 的题，一般都会涉及上、下、左、右四个方向查找；最终的考察点还是回归 bfs 或 dfs。

而为了实现查找，一般又会引出 recursive 方法辅助查询。

练习重点：1 - 深入理解 bfs dfs 思想；2 - 熟悉涉及矩阵时的 recursive 和 backtracking 代码套路。

熟悉 1 + 2 套路后，此类型中档难度题系列，也大多可以通过举一反三模仿思想解答……