图解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"为例，看一下具体的寻路历程：
四、代码实现
class Solution {
char[] wc; char[][] bc; int n, m;
public boolean exist(char[][] board, String word) {
wc = word.toCharArray();
bc = board;
n = board.length;
m = board[0].length;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (search(i, j, 0)) return true;
return false;
}
public boolean search(int row, int col, int index) {
if (index == wc.length) return true;
if (row < 0 || row >= n || col < 0 || col >= m) return false;
if (bc[row][col] != wc[index]) return false;
bc[row][col] = '\0'; // 标记已匹配
boolean result = 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]; // 回溯原值
return result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
