Feature #2: Possible Results

Description

In the previous lesson, we built a feature that will calculate the minimum number of conversions from the initial to the final word. Now, we need to fetch and display each new word after each conversion until we reach our end result. We’ll traverse the array and return the complete sequence of words after each conversion from start to end.

Here is an illustration of this process:

Solution

The previous feature involved finding the shortest path from a start node to an end node, but to solve this problem, we have to find all the possible paths from the start node to the end node.

We can use BFS to find the target word’s node from the initial node as we did for the previous feature. However, we can’t maintain the path from the start to the end node because BFS does a level order traversal. To get the paths, we can deploy a DFS (Depth First Search) algorithm, but since we are traversing a graph and not a tree, there will exist cycles. Many of the paths will not lead to the target word node, and the process will be extremely time-consuming.

In light of these observations, we can use the properties of both the BFS and DFS algorithms to build this feature. We will use BFS to construct the paths and DFS to find the shortest path.

Here is how we will implement this feature:

1. First, we’ll apply the BFS algorithm to find the correct word node by doing a level order traversal.

2. Next, we’ll replace each character in every word with one of the 26 English alphabets one at a time to check if that new word exists in our wordDict. If it exists, we can add that word to the next layer to be visited. At each level, we can ignore the non-visited nodes.

3. While implementing the BFS, we’ll create a directed subgraph on which we’ll later perform the DFS. In this subgraph, each node in layer i+1 points to the connected nodes in layer i.

4. During DFS traversal, if a node is equal to the target node, we can ...