Trick 3: how to get rid of TLE for BFS

Today I solved a BFS problem from Hackerrank.

I got TLE at the earlier beginning. I realized that using “for item in list” to traversing the list in a queue way is not so efficient. So I changed the implementation to queue, it works. In python, queue is supported by collections.deque

Problem:

Project Euler #244: Sliders

Project Euler #244: Sliders | HackerRank

Here is my code

One subtle thing I’d like to summarize is:

for BFS, if all shorest solutions are needed, we should add or new_state == des, to include multiple best solution into the queue.

if new_state not in seen or new_state == des:

Thanks for reading. I hope it helps.