赞
踩
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
示例 :
输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出:true
提示:
1、1 <= board.length <= 200;
2、1 <= board[i].length <= 200;
3、board 和 word 仅由大小写英文字母组成。
1、深度优先搜索(DFS):可理解为朝着某个方向一直递归下去,直到最后一个节点;
2、回溯:又称为试探法,按照某条件向前搜索,已达到某个目标;但当探索的某一步不符合条件时(比如不达目标),就退回上一步重新选择其他路径;
3、剪枝:当条件不符合要求时,则立即返回,避免后面多余的操作;
4、因为矩阵中每一个位置都可以是起点,所以遍历整个矩阵,确定起点,进行DFS操作。
1、剪枝
2、将矩阵中遍历的过节点置为空;(因为同一个单元格内的字母不允许被重复使用)
3、从上、左、下、右四个方向递归遍历矩阵;(只要有一个方向符合要求就返回true)
4、回溯:将节点恢复为原来的置;
5、返回结果。
class Solution {
public boolean exist(char[][] board, String word) {
// 获取单词的每一个字符
char[
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。