图解LeetCode——剑指 Offer 12. 矩阵中的路径

一、题目

• 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
• 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
• 例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

二、示例

2.1> 示例 1：

【输入】board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

【输出】true

2.2> 示例 2：

【输入】board = [["a","b"],["c","d"]], word = "abcd"

【输出】false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

三、解题思路

• 根据题目描述，我们需要在矩阵board中找到是否存在字符串单词word，那么我们第1个步骤要做的事情就是寻找单词word的第一个字符在board中的位置。然后再以这个字符作为起点去匹配word中的其他字符。
• 在这个对比过程中，我们会执行一些“错误的路径”。以下图为例，输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"；word的第1个字符是‘S’，那么我们会找到第2行第1列的‘S’，那么我们无论从它相邻的上、下、左、右都无法找到word的第2个字符‘E’，那么这个就是一条“错误的路径”。分析到这里，我们就很容易想到大致的解题思路就是——回溯。通过回溯我们才能从错误的路径中跳脱出来，继续去寻找矩阵board中的下一个字符‘S’，那么后续我们在第2行第4列找到了‘S’，然后发现可以找到一条“正确的路径”，就可以返回结果为true。

• 除了上面分析的内容之后，我们还需要注意一点，就是过滤后的格子我们不能重复经过，所以，每当我们经过某个格子（例如：row行col列）之后，可以暂时将其设置一个特殊值（例如：bc[row][col] = '\0'），那么如果发现是错误的路径，可以再将经过的格子值还原回去就可以了。
• 上面就是解题思路了，还是按照惯例，我们以输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"为例，看一下具体的寻路历程：

四、代码实现

classSolution {
char[] wc; char[][] bc; intn, m;
publicbooleanexist(char[][] board, Stringword) {
wc=word.toCharArray();
bc=board;
n=board.length;
m=board[0].length;
for (inti=0; i<n; i++) 
for (intj=0; j<m; j++) 
if (search(i, j, 0)) returntrue;
returnfalse;
    }
publicbooleansearch(introw, intcol, intindex) {
if (index==wc.length) returntrue;
if (row<0||row>=n||col<0||col>=m) returnfalse;     
if (bc[row][col] !=wc[index]) returnfalse;
bc[row][col] ='\0'; // 标记已匹配booleanresult=search(row-1, col, index+1) ||// 上search(row+1, col, index+1) ||// 下search(row, col-1, index+1) ||// 左search(row, col+1, index+1); // 右bc[row][col] =wc[index]; // 回溯原值returnresult;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」