752. Open The Lock

Medium

Description

有一個四位數的密碼鎖，初始狀態為 "0000"。每次操作可以將某一位數字向上或向下轉動一格。給定一組 deadends（死局狀態），求從 "0000" 到 target 的最少操作次數。若無法到達回傳 -1。

Example:

Input: deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202” Output: 6

Intuition#

每個狀態有 8 個鄰居（4 位各可加減 1），用 BFS 找最短路徑。

將每個四位數字串視為圖的節點
每次轉動一位數字產生一個相鄰狀態
避開 deadends，BFS 找到 target 的最短步數

Approaches#

⭐1: BFS#

概念: 從 “0000” 開始 BFS，每步產生 8 個鄰居狀態，跳過 deadends
時間複雜度: O(10^4 * 4)，最多 10000 個狀態
空間複雜度: O(10^4)

class Solution {
    fun openLock(deadends: Array<String>, target: String): Int {
        val dead = deadends.toHashSet()
        if ("0000" in dead) return -1
        if ("0000" == target) return 0

        val visited = HashSet<String>()
        visited.add("0000")
        val queue = ArrayDeque<String>()
        queue.add("0000")
        var steps = 0

        while (queue.isNotEmpty()) {
            steps++
            repeat(queue.size) {
                val cur = queue.removeFirst()
                for (i in 0 until 4) {
                    for (d in intArrayOf(-1, 1)) {
                        val arr = cur.toCharArray()
                        arr[i] = '0' + (arr[i] - '0' + d + 10) % 10
                        val next = String(arr)
                        if (next == target) return steps
                        if (next !in dead && next !in visited) {
                            visited.add(next)
                            queue.add(next)
                        }
                    }
                }
            }
        }
        return -1
    }
}

2: 雙向 BFS#

概念: 同時從起點和終點 BFS，每次擴展較小的一端，兩端相遇時即找到最短路徑
時間複雜度: O(10^4 * 4)（實際更快）
空間複雜度: O(10^4)

class Solution {
    fun openLock(deadends: Array<String>, target: String): Int {
        val dead = deadends.toHashSet()
        if ("0000" in dead || target in dead) return -1
        if ("0000" == target) return 0

        var beginSet = hashSetOf("0000")
        var endSet = hashSetOf(target)
        val visited = hashSetOf("0000", target)
        var steps = 0

        while (beginSet.isNotEmpty() && endSet.isNotEmpty()) {
            steps++
            if (beginSet.size > endSet.size) {
                val tmp = beginSet; beginSet = endSet; endSet = tmp
            }
            val nextSet = HashSet<String>()
            for (cur in beginSet) {
                for (i in 0 until 4) {
                    for (d in intArrayOf(-1, 1)) {
                        val arr = cur.toCharArray()
                        arr[i] = '0' + (arr[i] - '0' + d + 10) % 10
                        val next = String(arr)
                        if (next in endSet) return steps
                        if (next !in dead && next !in visited) {
                            visited.add(next)
                            nextSet.add(next)
                        }
                    }
                }
            }
            beginSet = nextSet
        }
        return -1
    }
}

🔑 Takeaways#

Pattern: 隱式圖 BFS – 狀態空間搜尋最短路徑
關鍵技巧: (digit + d + 10) % 10 處理數字 0-9 的循環；雙向 BFS 可大幅減少搜尋空間