leetcode-752.png

是一个比较典型的BFS题目

将题目意思拆解就可以得到
1.得到所有组合
2.所有组合然后进行剪枝
3.遇到目标 target 直接 return

首先第一步，得到所有组合，直接用BFS来进行操作
使用queue来存放每一层的节点，然后来一层一层的进行入队出队操作，得到所有组合

BFS

var openLock = function (deadends, target) {
    let visited = new Set(deadends)
    if(visited.has('0000')){
        // 因为初始条件就是 lock = '0000'
        // 如果此时在 deadens里面就遇到，那就直接 return -1
        return -1
    }
    visited.add('0000')
    // ['xxxx', 得到'xxxx'所需要的步数]
    let queue = [['0000', 0]]
    while (queue.length) {
        let [node, step] = queue.shift()
        // 如果此时拿到的 node 就是target 直接 return
        if (node === target) {
            return step
        }
        // 获取 node只用一步就可以获取的所有 lock 组合
        let nexts = getNextLock(node)
        for (let next of nexts) {
            // 剪枝，visited 里面是访问过，以及不符合条件的 deadends 组合
            // 不符合条件则 到 nexts 里面再拿出一个来进行判断
            if (!visited.has(next)) {
                // 标记访问过的节点
                visited.add(next)
                // 添加到 queue 里面，并且表明 步数
                queue.push([next, step + 1])
            }
        }
    }
    return -1
};
// 获取 current 的下一步的所有组合
var getNextLock = function (current) {
    let allLock = []
    for (let i = 0; i < 4; ++i) {
        // 注意处理 字符类型 以及 数值类型，以防错误
        // Number(current[i]) + 1) ！！！
        let up = current.substring(0, i) + (current[i] === '9' ? 0 : Number(current[i]) + 1) + current.substring(i + 1)
        let down = current.substring(0, i) + (current[i] === '0' ? 9 : Number(current[i]) - 1) + current.substring(i + 1)
        allLock.push(up)
        allLock.push(down)
    }
    return allLock
}

DFS

var openLock = function (deadends, target) {
    let visited = new Set(deadends)
    if (visited.has('0000')) {
        // 因为初始条件就是 lock = '0000'
        // 如果此时在 deadens里面就遇到，那就直接 return -1
        return -1
    }
    visited.add('0000')
    var dfs = function (current, step) {
        if (current === target) {
            return step
        }
        let minSteps = Infinity
        for (let next of getNextLock(current)) {
            if (!visited.has(next)) {
                visited.add(next)
                minSteps = Math.min(minSteps, dfs(next, step + 1))
                visited.delete(next)
            }
        }
    }
    let res = dfs('0000', 0)
    return res === Infinity ? -1 : res
};
// 获取 current 的下一步的所有组合
var getNextLock = function (current) {
    let allLock = []
    for (let i = 0; i < 4; ++i) {
        // 注意处理 字符类型 以及 数值类型，以防错误
        // Number(current[i]) + 1) ！！！
        let up = current.substring(0, i) + (current[i] === '9' ? 0 : Number(current[i]) + 1) + current.substring(i + 1)
        let down = current.substring(0, i) + (current[i] === '0' ? 9 : Number(current[i]) - 1) + current.substring(i + 1)
        allLock.push(up)
        allLock.push(down)
    }
    return allLock
}

这里是使用DFS的思路来解决这个问题，但是会报错，栈溢出

这里DFS以及BFS的时间复杂度以及空间复杂度都是 O(10^4)，4是锁的位数
因为DFS会压栈，如果不是最开始就检索到了，很容易会导致栈溢出
但是BFS不会，BFS一直在入队出队