我正在研究LeetCode上的打开锁定挑战：
你面前有一个带4个圆形轮子的锁。每个轮子有10个插槽：
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。轮子可以自由旋转和环绕：例如我们可以 转动'9''0'，或'0''9'.每个动作都包括将一个轮子转动一个槽。锁最初从
'0000'开始，一个代表4个轮子状态的字符串。您将获得
deadends死胡同的列表，这意味着如果锁显示任何这些代码，锁的轮子将停止转动，您将无法打开它。给定一个表示将解锁锁的车轮值的
target，返回打开锁所需的最小总圈数，如果不可能，则返回 -1。example1
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6
这是我的尝试：
var openLock = function(deadends, target) {
let res = 0;
let seen = []
let recursion = function(temp,counter=0){
if(deadends.includes(temp) || seen.includes(temp)) return
seen.push(temp)
if(temp ===target){
res = counter
return
}
for(let i=0; i<temp.length; i++){
let s1 = temp.substring(0, i) + (+temp[i]+1)%10 + temp.substring(i + 1)
let s2 = temp.substring(0, i) + (+temp[i]+9)%10 + temp.substring(i + 1)
recursion(s1,counter+1)
erecursion(s2,counter+1)
}
}
recursion('0000')
return res ?? -1;
};
我在这里的例子的输出是 2230，我不明白为什么。就好像counter变量值在每次递归调用中都会更新。
发生这种情况是因为您的代码将每个访问的组合标记为"已见"，而没有确保您通过最短路径到达该组合，因此您的代码永远不会尝试以较短的路径到达相同的组合。
对于示例输入，代码将按以下顺序访问组合：
0000
1000
2000
...
9000
0100
1100
2100
...
9100
0200
1200
...
...
。这一切都发生在没有回溯的情况下！由于您的for循环总会发现一些尚未访问过的可能性，因此递归只会加深，越来越深。
。最终它将命中目标组合，但通过一条非常长而深的递归路径。然后，该组合被标记为已见，因此您的代码永远不会考虑可能导致相同解决方案的较短路径。
深度优先与广度优先
虽然你可以让它与深度优先搜索一起工作，但用广度优先搜索来解决这个问题要容易一些，因为这更适合查找最短路径。使用深度优先搜索时，您只应将当前路径上的组合标记为"已见"。因此，当从递归中回溯时，那些更深的节点应该不被标记。
这是一个广度优先的解决方案：
var openLock = function(deadends, target) {
if (target == "0000") return 0; // boundary case
let seen = new Set(deadends);
if (seen.has("0000")) return -1; // boundary case
let frontier = ["0000"];
let res = 1;
while (frontier.length) {
let nextFrontier = [];
for (let combi of frontier) {
for (let dial = 0; dial < 4; dial++) {
for (let add = 1; add < 10; add += 8) {
let neighbor = combi.slice(0, dial) +
(+combi[dial] + add) % 10 +
combi.slice(dial+1);
if (!seen.has(neighbor)) {
if (neighbor == target) return res;
nextFrontier.push(neighbor);
seen.add(neighbor);
}
}
}
}
frontier = nextFrontier;
res++;
}
return -1;
};
该解决方案可以进一步优化。例如，add值现在总是首先是 1，然后是 9，但是当它"更接近"该表盘上的目标数字时，先尝试 9 可能是有益的。这将避免在另一个方向进行搜索的所有工作，因为在这种情况下，9 条道路很可能会导致更短的路径来解决。