LeetCode Open the Lock题递归实现counter异常递增问题求解

问题原因 #

你代码的问题主要有3个：

• 首先是笔误：erecursion(s2,counter+1) 这里多打了字符e，应该是recursion，如果没修正会直接抛出未定义错误，你输出2230说明大概率是粘贴代码时手滑写错。
• 核心逻辑错误：你采用了深度优先搜索（DFS）实现，DFS的遍历逻辑是一条路走到底，第一次找到目标时的路径不一定是最短路径，且你用全局变量res存储步数，后续更长的路径遍历到目标时会覆盖之前的数值，最终你得到的是最后一次遍历到目标的步数，不是最小步数，这是输出2230的核心原因。
• 已访问标记逻辑错误：你当前的代码是判断当前节点为死锁或已访问后直接返回，之后才把节点加入seen数组，会导致同一个节点被反复加入递归队列，产生大量冗余遍历，甚至触发栈溢出。正确的标记逻辑应该是进入递归第一时间就把节点标记为已访问，避免重复遍历。

正确实现思路 #

这道题求最少操作次数，属于典型的无权图最短路径问题，应该用广度优先搜索（BFS）实现：BFS按层遍历，每一层对应操作次数+1，第一次遍历到目标状态时的层数就是最小操作次数，直接返回即可，无需遍历所有路径。

修正后参考代码 #

var openLock = function(deadends, target) {
    const deadSet = new Set(deadends);
    if (deadSet.has('0000')) return -1;
    if (target === '0000') return 0;
    const queue = [['0000', 0]];
    const seen = new Set(['0000']);
    while (queue.length) {
        const [cur, step] = queue.shift();
        for (let i = 0; i < 4; i++) {
            // 向上拨一位
            const up = cur.substring(0,i) + ((+cur[i] +1) %10) + cur.substring(i+1);
            // 向下拨一位
            const down = cur.substring(0,i) + ((+cur[i] +9) %10) + cur.substring(i+1);
            if (up === target) return step +1;
            if (!deadSet.has(up) && !seen.has(up)) {
                seen.add(up);
                queue.push([up, step+1]);
            }
            if (down === target) return step +1;
            if (!deadSet.has(down) && !seen.has(down)) {
                seen.add(down);
                queue.push([down, step+1]);
            }
        }
    }
    return -1;
};

内容的提问来源于stack exchange，提问作者roglol