In my first attempt I tried to construct the graph in bfs traversal along with counting the minimum steps to reach the last word , and then use it to generate solution using dfs.

However this had a “OUT OF HEAP SPACE” error.

I managed to do the problem by not constructing the graph and checking if two strings differ in more than one character.

** What i’m concerned about** is how should I guess that a graph need not be constructed ? What if the strings were 10000’s character long won’t checking if two strings differ in more than one character (again and again) give a TLE?

I will be really grateful if someone can address this query .