Finding the shortest path from start to end word given list of words

Given list of array and start and end word as below:
   ["hot", "hit", "his", "hat"]
Start word: "hot"
End word: "his"

Find the shortest sequence starting the from start and ending the with end word.

The rule is, from the start word, each time you can only change one character,
and only use words from the given set, find out how to get to the end word.
In the above example, the sequence is:
   hot  -> hit -> his
(hat is not used)

for this example:
start = 'his'
end = 'hit'
input = ["his", "has", "hit", "hat"]

we can find this:
his -> has -> hat -> hit.

However: his -> hit is the sorted path.




Answer

1. Brute-frce search via DFS search $O(N!)$ (Please read the second option. Be patient)

To find the possible permutation of words starting from start and ending with end words, we need to first need to define the followings:

1. Condition to check if two words are one edit apart. 

In this question, we assume the length of words are the same. Therefore, only UPDATE will be possible action to transform one word to the other. (e.g. from his -> has. need to update i to a)

2. Ensure the path found is starting with the start word and ends with the end word.

To ensure this, re-arranging the given input such that it starts with the start word and ends with the end word.
It takes O(N) time.

3. Finding the shortest permutation.

Now, we have a list of words starting from the start and ending with the end. 

We can do the depth first search using backtracking and find the possible permutation that satisfies the requirements.

One optimization, we can make is that we only consider the permutation that starts with a start.
I did not think of this condition when I was writing the code. But it is good to bring up.

The overall running time of this algorithm is $$O(N!)$$ where N is the number of words

Here is the solution in python with the optimization.


Practice statistic

16:07: to write up the code (two bugs found after running - exit condition and variable)
05:50: write a test case and fix two bugs.

Did not think of optimization when writing the solution

UPDATE(2021-06-21): Solve the problem again. The initial idea was to use DFS to find the shortest path. I wanted to optimize the rearranging process using the hashtable but make one mistake of using the old indices before swapping the words. This resulted in the wrong answers and it took a while to debug.

Still, DFS is too inefficient and

2. Shortest path search via BFS $O(N^2)$ or less

The better way is to do the BFS to find the shortest path given that the weight of the edge between one word to the other is 1.

In that case, we need an additional Array, A to keep track of the shortest path value for each vertex, $V_{i}$ in A[$V_{i}]. We also need to keep track of whether each node (or word) had been explored. 

This algorithm will run in $O(N)$ time, where N is the number of words.

One catch is that we need to first build the graph by examining each word and comparing it against other words to see if there can be an edge between two words. This process will take $O(N^2)$. However, this can be done once during the initialization.

Here is the better algorithm using BFS: