安徽省建设厅执业资格注册中心网站,已经备案的网站新增ip怎么做,网页版微信文件传输助手,外贸销售渠道❓剑指 Offer 12. 矩阵中的路径
难度#xff1a;中等
给定一个 m * n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构…❓剑指 Offer 12. 矩阵中的路径
难度中等
给定一个 m * 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 提示
m board.lengthn board[i].length1 m, n 61 word.length 15board 和 word 仅由大小写英文字母组成
注意本题 79. 单词搜索 相同。
思路回溯法 使用回溯法backtracking进行求解它是一种暴力搜索方法通过搜索所有可能的结果来求解问题。 回溯法在一次搜索结束时需要进行回溯回退将这一次搜索过程中设置的状态进行清除从而开始一次新的搜索过程。
例如下图示例中从 f 开始下一步有 4 种搜索可能
如果先搜索 b需要将 b 标记为已经使用防止重复使用。在这一次搜索结束之后需要将 b 的已经使用状态清除并搜索 c。 代码(C、Java)
C
class Solution {
private:vectorpairint, int dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int m, n;bool check(vectorvectorchar board, vectorvectorint visited, int i, int j, string s, int k){if(board[i][j] ! s[k]) return false;if(k s.size() - 1) return true;visited[i][j] 1;bool ans false;for(auto dir : dirs){int cur_i i dir.first, cur_j j dir.second;if(cur_i 0 cur_i m cur_j 0 cur_j n visited[cur_i][cur_j] 0) {if(check(board, visited, cur_i, cur_j, s, k 1)){ans true;break;}}}visited[i][j] 0;return ans;}
public:bool exist(vectorvectorchar board, string word) {m board.size(); n board[0].size(); vectorvectorint visited(m, vectorint(n));for(int i 0; i m; i){for(int j 0; j n; j){if(check(board, visited, i, j, word, 0))return true;}}return false;}
};Java
class Solution {private int[][] dirs {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private int m, n;private boolean check(char[][] board, int[][] visited, int i, int j, String s, int k){if(board[i][j] ! s.charAt(k)) return false;if(k s.length() - 1) return true;visited[i][j] 1;boolean ans false;for(int[] dir : dirs){int cur_i i dir[0], cur_j j dir[1];if(cur_i 0 cur_i m cur_j 0 cur_j n visited[cur_i][cur_j] 0) {if(check(board, visited, cur_i, cur_j, s, k 1)){ans true;break;}}}visited[i][j] 0;return ans;}public boolean exist(char[][] board, String word) {m board.length; n board[0].length; int[][] visited new int[m][n];for(int i 0; i m; i){for(int j 0; j n; j){if(check(board, visited, i, j, word, 0))return true;}}return false;}
}运行结果 复杂度分析
时间复杂度一个非常宽松的上界为 O ( m n ∗ 3 l ) O(mn*3^l) O(mn∗3l)其中 m , n 为网格的长度与宽度l 为字符串 word 的长度。在每次调用函数 check 时除了第一次可以进入 4 个分支以外其余时间我们最多会进入 3 个分支因为每个位置只能使用一次所以走过来的分支没法走回去。空间复杂度 O ( m n ) O(mn) O(mn)。我们额外开辟了 O ( m n ) O(mn) O(mn) 的 visited 数组同时栈的深度最大为 O ( m i n ( l , m n ) ) O(min(l, mn)) O(min(l,mn))。。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
