Question:I have a somewhat complicated question. I am provided a list of words (each word has the same length). I am given two words into my function (StartNode and EndNode) and my task is to find the shortest path between the two (A follow-up would be how to collect all paths from startNode to EndNode). The words can only be connected if they have at most a 1 word difference. For example, TRIE and TREE could be connected since they only differ by one letter (I v E) but TRIE and TWEP can’t be connected since they have 2 character differences.
My solution was to first build an adjacency list, which I successfully implemented, and then compute a BFS to determine whether a path exists between the startNode and endNode. I am able to determine if a path exists but I’m unsure on how I can keep track of the path.
My attempt is as follows:
Best Answer:For anyone who stumbled upon this question, I did figure out a solution. A normal BFS just figures out if a path exists to the node and implicitly goes through the shortest traversal BUT if you want to show that traversal (path or length of path), it becomes necessary to keep two more counters.
In this case, I kept a counter of predecessor and a distance from source, my function therefore becomes:
Additionally, I also kept the distance dictionary. It would show the path to each node.
If you have better answer, please add a comment about this, thank you!