LeetCode 752：打開轉盤鎖 Open the Lock

題目：

你有一個帶有四個圓形撥輪的轉盤鎖。每個撥輪都有10個數字：

'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'

。每個撥輪可以自由旋轉：例如把

'9'

變為

'0'

，

'0'

'9'

。每次旋轉都隻能旋轉一個撥輪的一位數字。

鎖的初始數字為

'0000'

，一個代表四個撥輪的數字的字元串。

清單

deadends

包含了一組死亡數字，一旦撥輪的數字和清單裡的任何一個元素相同，這個鎖将會被永久鎖定，無法再被旋轉。

字元串

target

代表可以解鎖的數字，你需要給出最小的旋轉次數，如果無論如何不能解鎖，傳回 -1。

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:

'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'

. The wheels can rotate freely and wrap around: for example we can turn

'9'

to be

'0'

, or

'0'

'9'

. Each move consists of turning one wheel one slot.

The lock initially starts at

'0000'

, a string representing the state of the 4 wheels.

You are given a list of

deadends

dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a

target

representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

示例 1:

輸入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
輸出：6
解釋：
可能的移動序列為 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 這樣的序列是不能解鎖的，
因為當撥動到 "0102" 時這個鎖就會被鎖定。           

示例 2:

輸入: deadends = ["8888"], target = "0009"
輸出：1
解釋：
把最後一位反向旋轉一次即可 "0000" -> "0009"。           

示例 3:

輸入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
輸出：-1
解釋：
無法旋轉到目标數字且不被鎖定。           

示例 4:

輸入: deadends = ["0000"], target = "8888"
輸出：-1           

提示：

1. 死亡清單

   deadends

   的長度範圍為

   [1, 500]

   。
2. 目标數字

   target

   不會在

   deadends

   之中。
3. 每個

   deadends

   和

   target

   中的字元串的數字會在 10,000 個可能的情況

   '0000'

   到

   '9999'

   中産生。

Note:

1. The length of

   deadends

   will be in the range

   [1, 500]

   .

2. target

   will not be in the list

   deadends

3. Every string in

   deadends

   and the string

   target

   will be a string of 4 digits from the 10,000 possibilities

   '0000'

   to

   '9999'

解題思路：

題目要求給出最小的旋轉次數，應該就是用 BFS（廣度優先搜尋）解題了。初始字元串為

"0000"

那麼第二步就是

"1000" "9000" "0100" "0900" "0010" "0090" "0001" "0009"

共八個字元串，也就是說每一步的字元串撥動密碼擴充到下一步時可以得到八個新字元串。把它想象成圖的形式：很明顯相當于每個節點後有八個節點，用 BFS 每次走一個節點，直到達到目标節點，即是最短路徑。

另外需要注意：每次到要判斷節點是否為給出的死亡數字，并且把已周遊的節點也加入死亡數字以防止重複。這樣隻能将原數組形式的死亡數字轉為哈希表以減少查找操作的複雜度。用隊列暫存下一步需要周遊的節點。Java、python無法直接修改字元串裡的字元.Java可先轉換成 char 型數組，python可借助切片組裝新字元串。

Java：

class Solution {
    public int openLock(String[] deadends, String target) {
        HashSet<String> dead_set = new HashSet<>(Arrays.asList(deadends));//死亡數字轉為哈希表
        if (dead_set.contains("0000")) return -1;//死亡數字如果含有初始節點，傳回-1
        Queue<String> queue = new LinkedList<>();//隊列
        queue.add("0000");//加入初始節點
        int count = 0;//記錄步數
        while (!queue.isEmpty()) {//節點未通路完，隊列内的節點不為空
            int size = queue.size();//每一步節點數
            while (size-- > 0) {
                String tmp = queue.remove();//彈出頭節點
                if (target.equals(tmp)) return count;//如果與目标數相同，直接傳回步數
                char[] c = tmp.toCharArray();//轉為數組
                for (int j = 0; j < 4; j++) {//每次修改四位數字的一位
                    int i = c[j] - '0';//轉為int型
                    c[j] = (char) ('0' + (i + 9) % 10);//數字-1。餘數運算可防止節點為0、9時出現-1、10的情況
                    String s = new String(c);//得到新字元串
                    if (!dead_set.contains(s)) {//字元串不在死亡數字中時
                        queue.add(s);//添加到隊列作為下一步需要周遊的節點
                        dead_set.add(s);//下一步必通路該節點，是以可先加入到死亡數字
                    }
                    c[j] = (char) ('0' + (i + 11) % 10);//數字+1
                    s = new String(c);
                    if (!dead_set.contains(s)) {
                        queue.add(s);
                        dead_set.add(s);
                    }
                    c[j] = (char) ('0' + i);
                }
            }
            count++;
        }
        return -1;
    }
}           

Python：

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        #轉成哈希表
        dead_set = set(deadends)
        if '0000' in dead_set: return -1
        que = collections.deque(['0000'])
        count = 0
        while que:
            for x in range(len(que)):
                #從左取出頭節點
                tmp = que.popleft()
                if tmp == target: return count
                for i in range(4):
                    #分别存修改字元的左半部分字元串，待修改字元(轉成int)，右半部分字元
                    left, mid, right = tmp[:i], int(tmp[i]), tmp[i + 1:]
                    #j數字加一、減一撥動操作
                    for x in [-1, 1]:
                        s = left + str((mid + x) % 10) + right#切片拼接字元
                        if not s in dead_set:
                            dead_set.add(s)
                            que.append(s)
            count += 1
        return -1           

關注微.信.公.衆号：愛寫Bug，一起學習吖