進階圖論應用: 解開數字鎖 Open the Lock_Leetcode #752

Anne Nygård on Unsplash

題目敘述

題目會給我們一個4位數字的數字鎖，還有解鎖的密碼target，和陷阱數字deadends(假如遇到的話鎖會直接卡住，不能在撥動轉盤了)。

預設開始的狀態是0000，請問，最少要撥動轉盤幾次才能解鎖?

題目的原文敘述

測試範例

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation: 
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation: We cannot reach the target without getting stuck.

約束條件

Constraints:

• 1 <= deadends.length <= 500

陷阱數字的數量介於 1個~500個。

• deadends[i].length == 4

陷阱數字也是4-digits的數字。

• target.length == 4

解鎖密碼也是4-digits的數字。

• target will not be in the list deadends.

題目保證 解鎖密碼不會是陷阱數字。

• target and deadends[i] consist of digits only.

解鎖密碼和陷阱數字都是0~9的數字所構成。

演算法 映射到圖論中的最短路徑Shortest Path

可以把數字鎖的每個數字映射到圖論中的節點(代表一個狀態)。

可以透過轉動一格抵達的數字彼此有一條邊連著，權重為1，代表移動成本為一步，撥動轉盤一次。

那麼，原本題目所求: 從0000到解鎖密碼target的最小轉盤撥動次數 就等於 從0000到解鎖密碼target的最短路徑長度。

這是一張等權重的圖，BFS在等權重的圖先天具有尋找最短路徑的特質。

所以用BFS搭配N2 往上或往下撥動一格的位移向量，從出發點開始探索整張圖，當成功解鎖時，當下的步數 = 從0000到解鎖密碼target的最小轉盤撥動次數 = 從0000到解鎖密碼target的最短路徑長度。

程式碼 用BFS去找等權重圖中的最短路徑Shortest Path

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        
        # Starting number 0000 = 0
        start = 0000

        # Set of deadend number
        deadends = set( map(int, deadends) )

        # Target number
        target = int(target)

        # visited set to avoid repeated traversal
        seen = set([start])

        # Each digit can either go up or go down
        # 0 <-> 1 <-> 2 ... <-> 9 <-> 0
        rotation = (+1, -1)
        bfs_queue = deque( [ (start, 0) ] ) if start not in deadends else []

        # Try to open the lock with BFS to find the minimal count of rotations
        while bfs_queue:

            cur, step = bfs_queue.popleft()

            # Yeah! we meet the target number
            if cur == target:
                return step
            
            # Each round, we can pick one digit and rotate it
            for i in range(4):

                cur_digit = (cur // (10**i)) % 10

                # Each digit can either go up or go down
                for r in rotation:
                    offset = (( cur_digit + r + 10) % 10 - cur_digit) * (10 ** i)
                    next_state = cur + offset

                    # Skip when meeting deadend numbers
                    if next_state in deadends: continue

                    # Skip when this number is seen before
                    if next_state in seen: continue

                    bfs_queue.append( (next_state, step+1) )
                    seen.add( next_state )

        # ----------------------------------------------------
        # -1 stands for No solution
        return -1
            

複雜度分析 用BFS去找等權重圖中的最短路徑Shortest Path

時間複雜度:

從出發點開始探索整張圖，每個數字0000~9999最多拜訪一次，所需時間為O(10^4) = O(1) 常數級別。

空間複雜度:

空間成本耗費在BFS Queue上，Worst case是幾乎拜訪所有數字 = O(10^4) = O(1) 常數級別。

另外，建造deadends和seen也需要相對集合所需的空間，但是，密碼鎖的數字範圍0000~9999是固定的，所以，也可以是為常數空間O(1)。

關鍵知識點

可以把數字鎖的每個數字映射到圖論中的節點(代表一個狀態)。

可以透過轉動一格抵達的數字彼此有一條邊連著，權重為1，代表移動成本為一步，撥動轉盤一次。

那麼，原本題目所求: 從0000到解鎖密碼target的最小轉盤撥動次數 就等於 從0000到解鎖密碼target的最短路徑長度。

這是一張等權重的圖，BFS在等權重的圖先天具有尋找最短路徑的特質。

可以一起複習 最接近的迷宮出口 Nearest Exit from Entrance in Maze_Leetcode 1926這題，用到的都是同一個性質: 用BFS去找等權重的圖的最短路徑長度。

Reference:

[1] Open the Lock - LeetCode