LC752.打开转盘锁

思路：BFS + 如何去重

• root是根节点，它有几个孩子节点？
• 不考虑去重，root有8个孩子，一共4位，增加或者减少，有两种可能，所以一共可能的变化是8种。
• 因为题目中算的是最近距离，所以下意识想到BFS，第一次遍历到该节点，就是操作次数最小的。
• 第一次做的时候，自己乱想，去重其实直接在队列当中弹出头结点的时候，将其加入vis就行，然后加入队列的时候再判定即可。如果在计算可能的8个节点的时候，把本身的原字符串加入**vis**，那其实只是避免了往回走，没有防止重复遍历。
  
• 此题另外有一点值得注意：如何去记录节点所在层数：
  • 方法一：类似我这种方法，如果一层读完了，说明层数应该增加1
  • 方法二：利用一个map数据结构去记录状态， level[next_status] = level[old_status] + 1
  • 方法三：类似官方题解，每一个节点中记录两个数据：cur_val和cur_depth，在插入之后，更新其状态即可。q.push(nxt_val, nxt_depth + 1)

    代码：

class Solution:
    def numPrev(self, x: str) -> str:
        return "9" if x == "0" else str(int(x) - 1)    
    def numNext(self, x: str) -> str:
        return "0" if x == "9" else str(int(x) + 1)
    def getPossibleLock(self, originalString: str) -> List[str]:
        allPossibleLock = list()
        s = list(originalString)
        for i in range(4):
            num = s[i]
            s[i] = self.numPrev(num)
            allPossibleLock.append("".join(s))
            s[i] = self.numNext(num)
            allPossibleLock.append("".join(s))
            s[i] = num
        return allPossibleLock
    def openLock(self, deadends: List[str], target: str) -> int:
        root = "0000"
        q = collections.deque()
        q.append(root)
        dead, visLock = set(deadends), set()
        countOptions = 0
        if root in dead:
            return -1
        while len(q):
            for i in range(len(q)):
                curNode = q.popleft()
                if curNode == target:
                    return countOptions
                for element in self.getPossibleLock(curNode):
                    if element not in dead and element not in visLock:
                        q.append(element)
                        visLock.add(element)
            countOptions += 1
        return -1