I have commented the code at places. I can't understand why the code gives TLE. 1 test case gives TLE.I have tried to optimise it as much as I could but still TLE. Help would be appreciated. I have used breadth first search to solve the problem.The problem
Also what would be worst case complexity?
Code
Auto comment: topic has been updated by Forrest_Gump (previous revision, new revision, compare).
Try step by step.
You don't have to optimize, your implementation is incorrect.
Your BFS implementation is incorrect.
You should mark as a visited when it is in the queue, but you mark it when you got it extracted from the queue. This is the reason of TLE, you infinitely add to the queue values, that are already in the queue.
I have marked it visited twice. Even When it is pushed in the queue!
This can Help : CF BLOG Instead of storing string in Queue, try generating it when you arrive at the end, for generation of answer string , you can store (parent child )pair in map(STL). For Hint You can check : My Code
Thanks a lot!!! I didn't know about the complexity of adding char to string!
I have been watching your videos and streams lately they are pretty cool, keep the good work going :)