leetcode12 矩阵中的路径 回溯算法
2021-01-23 01:14
标签：leetcode 不能 存在 pos https string 匹配 length public 看到题目，一个变种的八皇后，在矩阵中寻找路径。 关于回溯的思路在博客： Burst Balloons（leetcode戳气球，困难）从指数级时间复杂度到多项式级时间复杂度的超详细优化思路（回溯到分治到动态规划 ） 中有非常详细的描述。 本题优化时间复杂度的关键在于剪枝，当越界、字符不匹配、路径已走过时立即停止搜索并返回，进行可行性剪枝。 有一点需要注意的时，我们有了三个坐标 x/y/strPointer ，但不能以这三个坐标为桩建立缓存复用局部结果。因为即使坐标对应了，已经走过的路径并不一定相同。 如果题目允许我们重复使用矩阵中的元素，则可以使用缓存来避免重复计算。 之所以回溯，都是为了记录之前操作对之后操作的影响。而存在这种影响则说明，如果要建立缓存，这些影响必须包含在缓存坐标中，通常这将会带来巨大的代价。 因此一旦使用了回溯，便很难再通过缓存优化我们的算法。 leetcode12 矩阵中的路径 回溯算法 标签：leetcode 不能 存在 pos https string 匹配 length public 原文地址：https://www.cnblogs.com/niuyourou/p/12885955.html
public boolean exist(char[][] board, String word) {
int strPoint = 0;
int xLength = board.length;
int yLength = board[0].length;
for (int i = 0; i ) {
for (int j = 0; j ) {
if (exist(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
public final boolean exist(char[][] board, String word, int x, int y, int strPointer) {
if (strPointer == word.length()) {
return true;
}
int xLength = board.length;
int yLength = board[0].length;
if (x = xLength || y = yLength || board[x][y] == ‘-‘ || board[x][y] != word.charAt(strPointer)) {
return false;
}
char boardChar = board[x][y];
board[x][y] = ‘-‘;
boolean re = exist(board, word, x + 1, y, strPointer + 1) ||
exist(board, word, x - 1, y, strPointer + 1) ||
exist(board, word, x, y + 1, strPointer + 1) ||
exist(board, word, x, y - 1, strPointer + 1);
board[x][y] = boardChar;
return re;
}
上一篇：算法学习：莫队
文章标题：leetcode12 矩阵中的路径 回溯算法
文章链接：http://soscw.com/index.php/essay/45677.html