专业网站建设加盟合作,搜索引擎seo,wordpress音乐插件mp3,做网站发布信息文章目录题目思路注意代码复杂度分析题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c…
文章目录题目思路注意代码复杂度分析题目
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如在下面的 3×4 的矩阵中包含单词 “ABCCED”单词中的字母已标出。 示例 1 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCCED” 输出true 示例 2 输入board [[“a”,“b”],[“c”,“d”]], word “abcd” 输出false 提示 1 board.length 200 1 board[i].length 200 board 和 word 仅由大小写英文字母组成 来源力扣LeetCode 链接https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof 思路
深度优先搜索 暴搜遍历矩阵中所有字符串。DFS 通过递归先朝一个方向搜到底再回溯至上个节点沿另一个方向搜索以此类推。
剪枝 在搜索中遇到 这条路不可能和目标字符串匹配成功 的情况例如此矩阵元素和目标字符不同、此元素已被访问则应立即返回称之为 可行性剪枝 。
DFS细节
递推工作 标记当前矩阵元素 将 board[i][j] 修改为 空字符 代表此元素已访问过防止之后搜索时重复访问。终止条件 返回 false (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 (3) 可合并至 (2) 。 返回 true k word.size() - 1 即字符串 word 已全部匹配。搜索下一单元格 朝当前元素的 上、下、左、右 四个方向开启下层递归使用 或 连接 代表只需找到一条可行路径就直接返回不再做后续 DFS 并记录结果至 res 。还原当前矩阵元素 将 board[i][j] 元素还原至初始值即 word[k] 。确保其他节点进行深搜时当前元素正常。返回值 返回布尔量 res 代表是否搜索到目标字符串。 注意
典型的深搜题目值得一提的是在写代码时发现一个小小的改动就能带来时间和空间的巨大优化可能这就是编程语言的魅力吧误。我们常说
拷贝传值较之引用传值
引用传值避免拷贝操作带来的时间与空间的额外开销。拷贝传值修改实参的拷贝而非实参本身从而确保实参的安全性。
在构建dfs函数时我们会修改board但最终也会将其复原因此调用board的安全性是可以保证的也就意味着可以使用引用传值。
而对于word我们根本就不会去修改它因此可以在声明时为代表其的形参赋予const属性并以引用传值的方式进行调用。
而对于i j k不将它们设置为引用传参的原因是在进行上、下、左、右四个方向的深搜时要传入一个表达式作为参数而非常量引用必须绑定到左值以i 1为例表达式的结果作为临时变量被绑定在临时量const int temp上而形参int i作为非常量引用是无法绑定一个常量引用绑定的对象的。
当
bool dfs(vectorvectorchar board, const string word, size_t i, size_t j, int k);时时间、空间效率 当
bool dfs(vectorvectorchar board, const string word, size_t i, size_t j, int k)时时间、空间效率 该用引用的时候一定要用引用这句话深深刻在心里。。。。 代码
class Solution {size_t rows, cols;bool dfs(vectorvectorchar board, const string word, size_t i, size_t j, int k){if(i rows || i 0 || j cols || j 0 || board[i][j] ! word[k]){return false;}if(k (word.size() - 1)){return true;}board[i][j] \0;bool res dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) ||dfs(board, word, i, j - 1, k 1) || dfs(board, word, i, j 1, k 1);board[i][j] word[k];return res;}
public:bool exist(vectorvectorchar board, string word) {rows board.size();cols board[0].size();for(size_t i 0; i rows; i){for(size_t j 0; j cols; j){bool falg dfs(board, word, i, j, 0);if(falg){return true;}}}return false;}
};复杂度分析 M, N 分别为矩阵行列大小 KK 为字符串 word 长度。 时间复杂度 O(MN3^K)
最差情况下需要遍历矩阵中长度为 K 字符串的所有方案时间复杂度为 O(3^K )矩阵中共有 MN 个起点时间复杂度为 O(MN)。 方案数计算 设字符串长度为 K 搜索中每个字符有上、下、左、右四个方向可以选择舍弃回头上个字符的方向剩下 3 种选择因此方案数的复杂度为 O(3^K)。 空间复杂度 O(K) 搜索过程中的递归深度不超过 K 因此系统因函数调用累计使用的栈空间占用 O(K) 因为函数返回后系统调用的栈空间会释放。最坏情况下 K MN递归深度为 MN 此时系统栈使用 O(MN) 的额外空间。
作者jyd 链接https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/ 来源力扣LeetCode
