題目敘述
題目會給我們一個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.
題目保證 解鎖密碼不會是陷阱數字。
targetanddeadends[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:
