国外房屋设计网站,网页建设与制作,网站建设龙头股,如何建立自己网站视频剑指 Offer#xff08;第2版#xff09;面试题 12#xff1a;矩阵中的路径 剑指 Offer#xff08;第2版#xff09;面试题 12#xff1a;矩阵中的路径解法1#xff1a;回溯 剑指 Offer#xff08;第2版#xff09;面试题 12#xff1a;矩阵中的路径
题目来源#x… 剑指 Offer第2版面试题 12矩阵中的路径 剑指 Offer第2版面试题 12矩阵中的路径解法1回溯 剑指 Offer第2版面试题 12矩阵中的路径
题目来源23. 矩阵中的路径
解法1回溯
回溯算法模板题。
我们先枚举单词的起点然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母‘*’以避免重复使用字符注意回溯是要把特殊字母改回原来的状态这也是回溯算法的精髓。
代码
class Solution
{
private:const int dx[4] {-1, 0, 1, 0};const int dy[4] {0, 1, 0, -1};public:bool hasPath(vectorvectorchar matrix, string str){// 特判if (matrix.empty())return false;int m matrix.size(), n m ? matrix[0].size() : 0;for (int i 0; i m; i)for (int j 0; j n; j)if (backtracking(matrix, str, 0, i, j))return true;return false;}// 辅函数 - 回溯bool backtracking(vectorvectorchar matrix, string str, int level, int x, int y){if (matrix[x][y] ! str[level])return false;if (level str.size() - 1)return true;char c matrix[x][y];matrix[x][y] *;for (int i 0; i 4; i){int r x dx[i], c y dy[i];if (r 0 r matrix.size() c 0 c matrix[0].size())if (backtracking(matrix, str, level 1, r, c))return true;}matrix[x][y] c;return false;}
};复杂度分析
时间复杂度O(m*n*3k)其中 m 和 n 分别是二维矩阵 matrix 的行数和列数。遍历二维矩阵 matrix 的每个元素作为单词的起点单词的每个字母一共有上下左右四个方向可以选择但由于不能走回头路所以除了单词首字母外仅有 3 种选择。
空间复杂度O(1)。
