在矩阵中寻找一个字符串应该怎么找？｜刷题打卡

在一个矩阵中寻找一个固定的字符串，你会怎么做呢？

原题链接剑指 Offer 12. 矩阵中的路径

相同解法主站链接：79. 单词搜索

一、先看题

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母已标出）。

[["a","b","c","e"],

["s","f","c","s"],

["a","d","e","e"]]

示例：

示例2：

提示：

• 1<=board.length<=200
• 1<=board[i].length<=200

二、整理思路

题目包含了不少信息和限制，我们先一点点分析，理清思路。

第一步：

确认输入输出：

输入：一个二维数组；输出：布尔值。

第二步

怎么处理输入才能得到输出？

在题干中的解释来看，其实就是找到一条有序的路径，而且这条路径经过每个格子时都是类似的判断条件，除此之外，这条路径不能走相同的格子。

从这两点分析，很容易就能想到，这个题应该能用递归来处理。并且需要某种方法来记录已经走过的格子的状态。

因此，得到了下面的算法：

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
function find(board, wordArr, status, i, j, idx) {
    //考虑边界情况以及字符对比和重复
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1 || board[i][j] != wordArr[idx] || status[i][j] == 0) return false
    //成功查找到最后一个字符
    if (idx == wordArr.length-1) return true
    status[i][j] = 0
    //上下左右依次查找
    res = find(board, wordArr, status, i + 1, j, idx + 1) || find(board, wordArr, status, i, j + 1, idx + 1) || find(board, wordArr, status, i - 1, j, idx + 1) || find(board, wordArr, status, i, j - 1, idx + 1)
    //只有没找到结果才会走这里，因此将字符状态复原
    status[i][j] = 1
    return res
}

var exist = function (board, word) {
    let status = []
    //值得注意的是，当fill中填充的值为引用类型时，
    //修改一个填充单位的值会修改所有的填充单位。
    //因此这里改用for循环来填充
    for(let i=0;i<board.length;i++){
        status.push(new Array(board[0].length).fill(1))
    }
    let wordArr = Array.from(word)
    for(let i=0;i<board.length;i++){
        for(let j=0;j<board[0].length;j++){
            if(find(board,wordArr,status,i,j,0)) return true
        }
    }
    return false
};

在自己解决的过程中，最难的就是理清DFS思路，false的情况是比较显眼的，但是返回true的条件当时却一时未能想到。还有一个点就是状态复原这个操作，最初一直没想好怎么处理，后来参考了题解，才想明白，无论他返回的是true或者false，我们统一在判断完之后对他进行复原就好了，这样下级的判断就不会影响到上级。

题解中还有一种能减少空间复杂度的方式，贴在下面供大家参考：

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
function find(board, wordArr, i, j, idx) {
    //考虑边界情况以及字符对比和重复
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[0].length - 1 || board[i][j] != wordArr[idx]) return false
    //成功查找到最后一个字符
    if (idx == wordArr.length-1) return true
    //直接修改原数组为空字符
    board[i][j] = '\0'
    //上下左右依次查找
    res = find(board, wordArr, i + 1, j, idx + 1) || find(board, wordArr, i, j + 1, idx + 1) || find(board, wordArr, i - 1, j, idx + 1) || find(board, wordArr, i, j - 1, idx + 1)
    //只有没找到结果才会走这里，因此将字符状态复原
    //将空字符复原
    board[i][j] = wordArr[idx]
    return res
}

var exist = function (board, word) {
    let wordArr = Array.from(word)
    for(let i=0;i<board.length;i++){
        for(let j=0;j<board[0].length;j++){
            if(find(board,wordArr,i,j,0)) return true
        }
    }
    return false
};

这个方法通过暂时性的修改原数组，减少了状态变量的空间消耗。但是在实际测试中，对数组的字符进行频繁修改反而增加了一些内存消耗，时间上总体来说要快一些，可能是因为减少了创建状态变量的时间。

三、总结

当题目复杂的时候，我们可以把题目中给出的条件分析一遍，找到边界条件，然后再根据恰当的思路进行算法分析，将复杂的题目简单化从而归纳到熟悉的体系中才是解题的正确思路。

一起加油吧！

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情