javascript - 打开锁 - LeetCode，为什么计数器在每次递归调用中不断增加？

Question

我正在处理 Open the lock LeetCode 上的挑战:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1

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变量值在每次递归调用中更新。

Answer 1

发生这种情况是因为您的代码将每个访问过的组合标记为“已看到”，而没有确保您通过最短路径到达该组合，因此您的代码永远不会尝试使用更短的路径到达相同的组合。
对于示例输入，您的代码将按以下顺序访问组合:

0000
1000
2000
...
9000
0100
1100
2100
...
9100
0200
1200
...
...

...所有这一切都发生在没有回溯的情况下!作为您的 for loop 总会找到一些还没有被访问过的可能性，递归只是加深，加深。
...最终它会命中目标组合，但需要通过非常长且深的递归路径。然后该组合被标记为可见，因此您的代码永远不会考虑可能导致相同解决方案的较短路径。
深度优先与广度优先
尽管您可以使用深度优先搜索使其工作，但使用广度优先搜索更容易解决此问题，因为它更适合查找最短路径。使用深度优先搜索，您应该只将当前路径上的组合标记为“已看到”。所以当从递归中回溯时，那些更深的节点应该没有标记。
这是广度优先的解决方案:

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 路很可能会导致更短的解决方案路径。