这道题和之前的回溯算法题目有两点不同
1、不再是统计path，而是验证结果，返回 True 和 False。
2、不再是单一方向回溯，由于是在矩阵中回溯，所以是四个方向，包括上下左右。

题目

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

注意测试样例： - 功能测试 - 边界值测试 - 特殊输入测试

def test_exist(self):
    # 测试用例
    # 功能测试：多行多列矩阵中存在或不存在的路径
    # 边界值测试：矩阵只有一行或只有一列 矩阵和路径中的所有字母都相同
    # 特殊输入测试：[]
    board = [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],   # 功能测试
            [["a","b"],["c","d"]],   # 功能测试
            [["a", "a", "a"]],  # 边界值测试
            [["a"], ["a"], ["a"]],  # 边界值测试
            [["a", "a", "a"]],  # 边界值测试
            [["a"], ["a"], ["a"]],  # 边界值测试
            [],  # 特殊输入测试
            [[]],  # 特殊输入测试
    ]
    word = ["ABCCED", "abcd", "aaa", "aaa", "bbb", "bbb", "123", "123",]
    answers = [True, False, True, True, False, False, False, False]
    res = []
    for i in range(len(board)):
        res.append(self.test_class.exist(board[i], word[i]))
    self.assertEqual(res, answers)

def tearDown(self):
    del self.test_class

示例

示例:

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

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

考察知识点

回溯算法
考查应聘者对回溯法的理解。通常在二维矩阵上找路径这类问题都可以应用回溯法解决。
考查应聘者对数组的编程能力。我们一般都把矩阵看成一个二维的数组。只有对数组的特性充分了解，才有可能快速、正确地实现回溯法的代码。

核心思想

方法一、回溯算法
典型的深度优先遍历 DFS 的应用，原二维数组就像是一个迷宫，可以上下左右四个方向行走，我们以二维数组中每一个数都作为起点和给定字符串做匹配，我们还需要一个和原数组等大小的 visited 数组，是 bool 型的，用来记录当前位置是否已经被访问过，因为题目要求一个 cell 只能被访问一次（题干中说”同一个单元格内的字母不允许被重复使用“）。
如果二维数组 board 的当前字符和目标字符串 word 对应的字符相等，则对其上下左右四个邻字符分别调用 DFS 的递归函数，只要有一个返回 true，那么就表示可以找到对应的字符串，否则就不能找到。

特点：这道题和之前的回溯算法题目有两点不同
1、不再是统计path，而是验证结果，返回 True 和 False。
2、不再是单一方向回溯，由于是在矩阵中回溯，所以是四个方向，包括上下左右。

注意：题目的意思是，只要你的搜索返回 True 才返回，如果全部的格子都搜索完了以后，都返回 False ，才返回 False。

算法

特判 board 为空的情况，声明 visited 矩阵。
双层循环遍历 board 中的每一个位置，调用回溯函数判断从当前位置出发，能否找到该字符串。
- 进入 backtrack，判断当前 depth 是否已经到最底下一层。如果是，就返回 True 。
- 如果不是就先判断 row、col等变量是否越界，是否已经访问过该位置，该位置如果没有访问，那么该位置的字母目标字母一样，越界、已访问、不是目标字母，返回False。
- 如果既没有越界，该位置也没有被访问，且和目标字母一样，就进行visited 选择
- 向上下左右四个方向回溯，保留回溯结果 res 。
- 结束回溯，撤销选择。
- 返回回溯结果 res 。

改进

我们还可以不用 visited 数组，直接对 board 数组进行修改，将其遍历过的位置改为井号，记得递归调用完后需要恢复之前的状态。

Python版本

方法一的实现

from typing import List


class Solution:
    def backtrack(self, board, word, depth, row, col, visited):
        if depth == len(word):  return True
        rows, cols = len(board), len(board[0])
        if row < 0 or col < 0 or row >= rows or col >= cols or visited[row][col] or board[row][col] != word[depth]:
            return False
        visited[row][col] = True # 选择
        res = self.backtrack(board, word, depth + 1, row - 1, col, visited) or self.backtrack(board, word, depth + 1, row + 1, col, visited) or self.backtrack(board, word, depth + 1, row, col - 1, visited) or self.backtrack(board, word, depth + 1, row, col + 1, visited)  # 开始回溯
        visited[row][col] = False  # 回溯结束 撤销选择
        return res

    def exist(self, board: List[List[str]], word: str) -> bool:
        if not len(board) or not len(board[0]):  return False
        rows = len(board)
        cols = len(board[0])
        visited = [[False for _ in range(cols)] for _ in range(rows)]
        for row in range(rows):
            for col in range(cols):
                if self.backtrack(board, word, 0, row, col, visited):  return True
        return False

Input = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
Input1 = ["ABCCED", "SEE", "ABCB"]
Answer = [True, True, False]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        reslut = solution.exist(Input, Input1[i])
        print(reslut == Answer[i])

时间复杂度：\(O(m \times n \times k \times 4)\)，m为行数，n为列数，k为word的长度，内层的回溯函数，每次都向四个方向进行回溯。
空间复杂度：\(O(n \times m)\)，需要额外的 visited 矩阵。
执行用时 :292 ms, 在所有 Python3 提交中击败了74.79%的用户
内存消耗 :14.2 MB, 在所有 Python3 提交中击败了13.02%的用户

简单优化版本

class Solution:
    def backtrack(self, board, word, depth, row, col):
        if depth == len(word):  return True  # 终止条件
        rows, cols = len(board), len(board[0])
        if row < 0 or col < 0 or row >= rows or col >= cols or board[row][col] != word[depth]:
            return False
        char = board[row][col]
        board[row][col] = "#" # 选择
        res = self.backtrack(board, word, depth + 1, row - 1, col) or \
        self.backtrack(board, word, depth + 1, row + 1, col) or \
        self.backtrack(board, word, depth + 1, row, col - 1) or \
        self.backtrack(board, word, depth + 1, row, col + 1)  # 回溯
        board[row][col] = char  # 撤销选择
        return res

    def exist(self, board: List[List[str]], word: str) -> bool:
        if not len(board) or not len(board[0]):  return False  # 特判
        rows = len(board)
        cols = len(board[0])
        for row in range(rows):
            for col in range(cols):
                if self.backtrack(board, word, 0, row, col):  return True
        return False

时间复杂度：\(O(m \times n \times k \times 4)\)，m为行数，n为列数，k为word的长度，内层的回溯函数，每次都向四个方向进行回溯。
空间复杂度：\(O(1)\)，无额外空间。
执行用时 :252 ms, 在所有 Python3 提交中击败了82.69%的用户
内存消耗 :14.2 MB, 在所有 Python3 提交中击败了14.18%的用户

2020-05-01 剑指offer重新尝试该题目按照：终止条件 -> 选择列表 -> 进行选择 -> 回溯 -> 撤销选择 的顺序进行代码编写，更加简洁清晰。

import unittest
from typing import List

class Solution():

    def exist(self, board: List[List[str]], word: str) -> bool:
        """ *** 
        :param board: List[int]
        :param word: str
        :return: bool
        """
        if not len(board) or (len(board) == 1 and len(board[0])==0):  return False
        n = len(board)  # rows
        m = len(board[0])  # cols
        used = [[True for _ in range(m)] for _ in range(n)]

        # x为行坐标 y为列坐标
        def backtrack(depth=0, x=0, y=0,):
            # 终止条件
            if depth == len(word):
                return True
            hasPath = False
            if  0 <= x < n and 0 <= y < m and used[x][y] and board[x][y] == word[depth]:  # 选择列表
                used[x][y] = False  # 进行选择
                hasPath = backtrack(depth+1, x, y+1) or \
                          backtrack(depth+1, x, y-1) or \
                          backtrack(depth+1, x+1, y) or \
                          backtrack(depth+1, x-1, y)  # 回溯
                used[x][y] = True  # 撤销选择
            return hasPath

        for i in range(n):
            for j in range(m):
                if backtrack(0, i, j):
                    return True

        return False


class Test_Solution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()
    
    def test_exist(self):
        # 测试用例
        # 功能测试：多行多列矩阵中存在或不存在的路径
        # 边界值测试：矩阵只有一行或只有一列 矩阵和路径中的所有字母都相同
        # 特殊输入测试：[]
        board = [[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],   # 功能测试
                [["a","b"],["c","d"]],   # 功能测试
                [["a", "a", "a"]],  # 边界值测试
                [["a"], ["a"], ["a"]],  # 边界值测试
                [["a", "a", "a"]],  # 边界值测试
                [["a"], ["a"], ["a"]],  # 边界值测试
                [],  # 特殊输入测试
                [[]],  # 特殊输入测试
        ]
        word = ["ABCCED", "abcd", "aaa", "aaa", "bbb", "bbb", "123", "123",]
        answers = [True, False, True, True, False, False, False, False]
        res = []
        for i in range(len(board)):
            res.append(self.test_class.exist(board[i], word[i]))
        self.assertEqual(res, answers)
    
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":

    # 代码提交模式
    # import sys
    # res = []
    # s = sys.stdin.readline().strip("\n") 
    # while s != "":
    #     res.append(s)
    #     s = sys.stdin.readline().strip("\n")
    # 关键参数获取根据实际情况而定
    # items = [int(x) for x in res[1].split(' ')]
    # solution = Solution()
    # print(solution.getMaxArea(items))

    # 代码编写模式
    unittest.main()

参考连接

Grandyang

LeetCode 剑指offer

回溯算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode 80. 删除排序数组中的重复项 II（中）上一篇

LeetCode 82. 删除排序链表中的重复元素 II（中）下一篇

LeetCode 79. 单词搜索（中） & 剑指offer 面试题12. 矩阵中的路径（中）

题目

示例

考察知识点

核心思想

Python版本