iâm interested if we need a bfs_map at all. i feel that we can just use regular visited set() and then to keep track of how many steps use a steps/level variable that is either kept in the queue as a tuple (step, combo_number) or just is a variable incremented after exploring the entire queueâs current nodes. i feel that might be more in line with previous solutions, but an explanation of why you do this would be interesting! i was just most confused why you would do bfs_map[top] + 1 because using a hashmap implies that we might need to quickly look up the steps for this specific combo once again? but we only ever each combo once right :o

We can start regular BFS with visited initialized to trapped_combos and â0000â. For this problem, we need to avoid trapped_combos, since we already avoid visited, we can combine into one.

We can simplify the logic for ârotatingâ to single function, with +1 and -1 offsets. Neighbors will be forward_combos + backward_combos.

The solution is definitely not neatâŚ

Made your proposed alternate solution below. Itâs a modified version of this submission on LC, edited for readability: https://leetcode.com/problems/open-the-lock/discuss/110232/Accepted-PythonJava-BFS-%2B-how-to-avoid-TLE

from typing import List

from collections import deque

def num_steps(combo: str, trapped_combos: List[str]) â int:

```
# we can solve the problem of integer rollover
# by using the % operator with 10.
def get_next_combos(src):
res = []
for i, digit in enumerate(src):
num = int(digit)
res.append(src[:i] + str((num - 1) % 10) + src[i+1:])
res.append(src[:i] + str((num + 1) % 10) + src[i+1:])
return res
visited, queue = set(trapped_combos), deque(['0000'])
depth = -1
while queue:
size = len(queue)
depth += 1
for _ in range(size):
cur_combo = queue.popleft()
if cur_combo == combo:
return depth
if cur_combo in visited:
continue
visited.add(cur_combo)
queue.extend(get_next_combos(cur_combo))
return -1
```

Where did you get 10^4 as the time complexity?

// Implementation in Javascript

function numSteps(combo, trappedCombos) {

function getNeighbors(combo) {

let a = combo.split(ââ).map(x => parseInt(x, 10));

let res = [];

let delta = [1,-1];

for (let i=0; i<4; i++) {

for (let j=0; j<delta.length; j++) {

let temp = a[i];

a[i] = (a[i] + delta[j] + 10)%10;

if (!trappedCombos.includes(a.join(ââ))) res.push(a.join(ââ));

a[i]=temp; // Resetting the value;

}

}

return res;

}

```
let visited = new Set(['0000']);
let queue = ['0000'];
let steps = -1;
while (queue.length) {
steps++;
let n = queue.length;
for (let i=0; i<n; i++) {
let node = queue.shift();
if (node === combo) return steps;
for (let x of getNeighbors(node)) {
if (visited.has(x)) continue;
visited.add(x);
queue.push(x);
}
}
}
return -1;
```

}

Yo, I am amazed by the bfs_map part in the solution.

I initially come up with a solution that use BFS with kind of a level order search (8 states per level) and keep a variable steps = 0 and increase by 1 for every level. I got all answers correct except test case 3 which was time limit exceeded. After I change my visited set to a visited dictionary (bfs_map in the solution) I passed test case 3.

Can someone explain to me why doing addition of steps for every state and save the results in a hashmap is faster than I just keep a variable and do the addition of steps per level? I know taking a value from hashmap cost O(1) time but it seems to me that there are much more work to be done compare to just keeping a step variable.

FYI - I followed the âgetting neighborsâ pattern to keep the coding style consistent with previous questions

```
# WRITE YOUR BRILLIANT CODE HERE
def get_nbs(comb: str):
res = []
for i in range(4):
k = int(comb[i])
k += 1
if k > 9:
k = 0
s = comb[0:i] + str(k) + comb[i+1:]
res.append(s)
k = int(comb[i])
k -= 1
if k < 0:
k = 9
s = comb[0:i] + str(k) + comb[i+1:]
res.append(s)
#print(f"nbs of {comb}: {res}")
return res
q = deque(["0000"])
steps_map = {"0000": 0}
trapped_combos_set = set(trapped_combos)
while len(q) > 0:
qlen = len(q)
for _ in range(qlen):
prev = q.popleft()
for nb in get_nbs(prev):
if nb not in trapped_combos_set and nb not in steps_map:
q.append(nb)
steps_map[nb] = steps_map[prev] + 1
if nb == combo:
return steps_map[nb]
return -1
```

How come algomonster throws an error when trying to pass a string to the funtion below? Running this in an ipython console works as intended with no errors whatsoever.

```
def get_neighbors(combo):
res = []
for i in range(4):
k = int(combo[i])
if k + 1 > 9:
s1 = combo[0:i] + '0' + combo[i + 1:]
else:
s1 = combo[0:i] + str(k + 1) + combo[i + 1:]
res.append(s1)
if k - 1 < 0:
s2 = combo[0:i] + '9' + combo[i + 1:]
else:
s2 = combo[0:i] + str(k - 1) + combo[i + 1:]
res.append(s2)
return res
```

The error is below:

```
Traceback (most recent call last):
File "solution.py", line 44, in <module>
res = num_steps(combo, trapped_combos)
File "solution.py", line 31, in num_steps
for neighbor in get_neighbors(node):
File "solution.py", line 13, in get_neighbors
s1 = combo[0:i] + '0' + combo[i + 1:]
TypeError: can only concatenate list (not "str") to list
```

Iâd also like to know this. It doesnât seem to make sense.

My solution without a dictionary

# WRITE YOUR BRILLIANT CODE HERE

```
def get_neighbors(num):
res = []
for i in range(4):
next_digit = int(num[i]) + 1
if next_digit > 9:
next_digit = 0
prev_digit = int(num[i]) - 1
if prev_digit < 0:
prev_digit = 9
next_num = num[:i] + str(next_digit) + num[i+1:]
prev_num = num[:i] + str(prev_digit) + num[i+1:]
res.append(str(prev_num))
res.append(str(next_num))
return res
if combo == "0000":
return 0
q = deque(["0000"])
trap_set = set(trapped_combos)
visited = set(["0000"])
tests = 0
while q:
for _ in range(len(q)):
test_combo = q.popleft()
if combo == test_combo:
return tests
for nbr in get_neighbors(test_combo):
if nbr in visited or nbr in trap_set:
continue
visited.add(nbr)
q.append(nbr)
tests += 1
return -1
```

Solution that I found to be more readable:

def rotate(combo, index, amount):

copy = [int(x) for x in combo]

digit = copy[index] + amount

if digit > 9:

copy[index] = 0

elif digit < 0:

copy[index] = 9

else:

copy[index] = digit

return ââ.join([str(x) for x in copy])

def num_steps(target: str, traps: List[str]) â int:

q = deque([â0000â])

visited = {}

steps = 0

while len(q) > 0:

n = len(q)

for _ in range(n):

current = q.popleft()

if current in visited:

continue

visited[current] = True

if current in traps:

continue

if current == target:

return steps

```
for rotate_index in range(4):
q.append(rotate(current, rotate_index, 1))
q.append(rotate(current, rotate_index, -1))
steps += 1
return -1
```

why do we keep track of steps for each combo in a dictionary? wouldnât increasing âstepâ variable after each âlevelâ be simpler and more memory efficient? In the end we are interested only in the minimum number of steps for a single combination? \

moreover, we could initialise âvisitedâ set with prohibited combinations and have a single check: new_combo in visited instead of splitting it for already vistited and prohibited combos \

My solution: \

def num_steps(target_combo: str, trapped_combos: List[str]) â int:

def get_neighbours(combo):

for i in range(4):

yield combo[0:i] + str((int(combo[i]) + 1) % 10) + combo[i+1:]

yield combo[0:i] + str((int(combo[i]) - 1) % 10) + combo[i+1:]

```
seed = "0000"
visited = set(trapped_combos)
visited.add(seed)
q = deque([seed])
steps = 0
while len(q) > 0:
for _ in range(len(q)):
combo = q.popleft()
if combo == target_combo:
return steps
for n in get_neighbours(combo):
if n in visited:
continue
visited.add(n)
q.append(n)
steps += 1
return -1
```

mine implementation (comment above) using a visited set and steps update after each level passes all tests

Why do we need to turn the trapped_combos into a set? canât we just leave it as a list, since weâre only checking if a combo is in it?

OH its because, to check the existence of an item in a SET can be done in O(1) time whereas in a LIST its O(n)

from typing import List

from collections import deque

def num_steps(target_combo: str, trapped_combos: List[str]) â int:

# WRITE YOUR BRILLIANT CODE HERE

# 1- each code have 8 neighber (4 forward and 4 backworld)

# 2- get_neighbor from each case above

# 3- bfs to determine the min number of digit change to unlock

# need to parse all element in the bfsâqueue to process

# entire level inoredr to increment the steps by 1

```
def get_neighbor(combo):
for i in range(4):
yield combo[0:i] + str((int(combo[i]) + 1) % 10) + combo[i+1:]
yield combo[0:i] + str((int(combo[i]) - 1) % 10) + combo[i+1:]
def bfs(target_combo, trapped_combos):
visited = set(trapped_combos)
start = "0000"
visited.add(start)
Try_nums = 0
q = deque([start])
while len(q):
for _ in range(len(q)):
combo = q.popleft()
if combo == target_combo:
return Try_nums
for nieghbor in get_neighbor(combo):
if nieghbor in visited:
continue
q.append(nieghbor)
visited.add(nieghbor)
Try_nums += 1
# Can't open it without triggering the trap
return -1
return bfs(target_combo, trapped_combos)
```

Can someone help please:

I just realized that when I finish a problem and click on the âMark as Completedâ button. My code/my Solution it disrepair from âTry it yourselfâ Does any one facing this? and I can we recover our solution that we did for previous exercises ?

Thank you