如何制作学校网站,常州建设局网站为什么打不开,中移电子商务有限公司为什么扣款,山东省建设工会网站一、题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平相…一、题目
给定一个 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.lengthn board[i].length1 m, n 61 word.length 15board 和 word 仅由大小写英文字母组成
三、解题思路
根据题目描述我们需要在矩阵board中找到是否存在字符串单词word那么我们第1个步骤要做的事情就是寻找单词word的第一个字符在board中的位置。然后再以这个字符作为起点去匹配word中的其他字符。
在这个对比过程中我们会执行一些“错误的路径”。以下图为例输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEEword的第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, index1) || // 上search(row1, col, index1) || // 下search(row, col-1, index1) || // 左search(row, col1, index1); // 右bc[row][col] wc[index]; // 回溯原值return result;}
} 今天的文章内容就这些了 写作不易笔者几个小时甚至数天完成的一篇文章只愿换来您几秒钟的 点赞 分享 。 更多技术干货欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享每天更新」
