Mark As Completed Discussion

We can look at this problem as a search problem of an undirected graph, where each node represents a word. We'll denote the start state by startW and goal state by endW. Two adjacent nodes are those that can be transformed into one another and have a difference of only one character.

To find the shortest sequence of words from the start to the goal state, we'll do a breadth first search. To implement breadth first search, a queue data structure is required. The figure below shows how search proceeds. The start state is four and goal state is hoop. The search is initialized by pushing the word four into the queue.

The search algorithm pops each word from the queue in a first in first out manner. In our example, the four is popped and its adjacent words are searched in the dictionary. Three such words are found, i.e., foum, hour and cour, which are again pushed into the queue one by one. This process is repeated till either the goal state is found or the entire dictionary has been searched.

Note that a search tree is implicitly being built, i.e., it is not physically present in memory, but its implicit representation is there. The queue is the data structure that keeps track of all nodes that need to be explored in a breadth first manner. This queue is also shown in the figure as Q.

Our Explanation