推 pandix: node定义怪怪的 上下转应该是for e in dic[int(lock[i])] 04/22 11:46
→ pandix: 之类的东西 04/22 11:46
感谢面包屌
修改一下就过了
Python Code:
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
dic = defaultdict(list)
for i in range(10):
if i == 9:
dic[9].append(0)
dic[0].append(9)
else:
dic[i].append(i+1)
dic[i+1].append(i)
q = deque()
q.append(("0000",0))
visited = set(deadends)
while q:
lock,step = q.popleft()
if lock == target:
return step
if lock in visited:
continue
visited.add(lock)
for i in range(4):
for e in dic[int(lock[i])]:
s = lock[:i]+str(e)+lock[i+1:]
if s not in visited:
q.append((s,step+1))
return -1
不过时间空间都很粪 渍