网站开发的兼职网站,湛江网站模板,成都好的网站设计公司,建设银行住房租赁代表品牌是什么【问题描述】[中等]
请设计一个函数#xff0c;用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始#xff0c;每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格#xff0c;那么该路径不能再次进入…【问题描述】[中等]
请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径路径中的字母用加粗标出。[[a,b,c,e],
[s,f,c,s],
[a,d,e,e]]但矩阵中不包含字符串“abfb”的路径因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后路径不能再次进入这个格子。示例 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
【解答思路】
DFS 时间复杂度
class Solution {public boolean exist(char[][] board, String word) {char[] words word.toCharArray();for(int i 0; i board.length; i) {for(int j 0; j board[0].length; j) {if(dfs(board, words, i, j, 0)) return true;}}return false;}boolean dfs(char[][] board, char[] word, int i, int j, int k) {if(i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! word[k]) return false;if(k word.length - 1) return true;char tmp board[i][j];board[i][j] /;boolean 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] tmp;return res;}
}归搜索匹配字符串过程中需要 board[i][j] ‘/’ 来防止 ”走回头路“ 。当匹配字符串不成功时会回溯返回此时需要board[i][j] tmp 来”取消对此单元格的标记”。 在DFS过程中每个单元格会多次被访问的 board[i][j] /只是要保证在当前匹配方案中不要走回头路。 一层一层向下递归来进行字符串匹配的回溯的时候要“释放“这个单元格。匹配失败或者成功都会执行 board[i][j] tmp 匹配成功也需要将 True 结果一层一层返回直至起始点以获取匹配成功的结果 class Solution {private int[][] direct {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};private boolean[][] visited;public boolean exist(char[][] board, String word) {char[] words word.toCharArray();int row board.length;int col board[0].length;this.visited new boolean[row][col];for (int i 0; i row; i) {for (int j 0; j col; j) {if (dfs(board, i, j, words, 0)) {return true;}}}return false;}private boolean dfs(char[][] board, int x, int y, char[] word, int index) {if (board[x][y] word[index]) {if (index 1 word.length) {return true;}visited[x][y] true;for (int i 0; i 4; i) {int newX x direct[i][0];int newY y direct[i][1];if (inArea(newX, newY, board.length, board[0].length) !visited[newX][newY]) {if (dfs(board, newX, newY, word, index 1)) {return true;}}}visited[x][y] false;}return false;}private boolean inArea(int x, int y, int row, int col) {return x 0 y 0 x row y col;}
}【总结】
1.细节
1.1 方向数组 private int[][] direct {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; 1.2 char[] words word.toCharArray(); 替代Sting.charAt()charAt每次都要检查边界 1.3 边界判定 private boolean inArea(int x, int y, int row, int col) { return x 0 y 0 x row y col; } }
2.回溯 遍历时对原结果有影响 在dfs递归前后置状态-恢复状态 visited[x][y] true;dfsvisited[x][y] false;3. 算法原理
深度优先搜索 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归先朝一个方向搜到底再回溯至上个节点沿另一个方向搜索以此类推。 剪枝 在搜索中遇到 这条路不可能和目标字符串匹配成功 的情况例如此矩阵元素和目标字符不同、此元素已被访问则应立即返回称之为 可行性剪枝 。
转载链接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/
