题解 | #开锁#

bfs，将存在队列中密码的每一位进行操作，直到队列为空或达到目标值,初始时队列和记录已存在的密码集合均为 "0000"

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param vec string字符串一维数组 
# @param tar string字符串 
# @return int整型
#
class Solution:
    def open(self , vec: List[str], tar: str) -> int:
        # write code here
        queue = ["0000"]
        visited = set("0000")
        res = 0
        while queue:
            nxt = []
            for q in queue:
                if q == tar:
                    return res
                if q in vec:
                    continue
                for i in range(4):
                    t = int(q[i])
                    if t == 9:
                        t = 0
                    else:
                        t += 1
                    s = q[:i] + str(t) + q[i + 1:]
                    if s not in vec and s not in visited:
                        visited.add(s)
                        nxt.append(s)
                    t = int(q[i])
                    if t == 0:
                        t = 9
                    else:
                        t -= 1
                    s = q[:i] + str(t) + q[i + 1:]
                    if s not in vec and s not in visited:
                        visited.add(s)
                        nxt.append(s)
            queue = nxt
            res += 1
        return -1