Problem:
Suppose you a given a dictionary of n words of length 5 and you would like to nd the minimum number of one-character changes that allows you do go from a starting words to a target word t, subject to the constraint that whenever you change a character the resulting word has to be in the dictionary. As an example, here's a sequence of one-character changes that allows you to go from the starting word coins to the target word money:
coins
corns
cores
cones
coney
money
Solution:
Lets try to figure out a efficient algorithm to solve the above given algorithm. As per the given problem we have n words of length 5 each, and we would like to find a minimum number of one character changes that allow you to go from a "source word" to a "target word". In order to solve such a problem we can follow the below approach:
Below is a part of the graph that can be made out of the n words given.
Suppose you a given a dictionary of n words of length 5 and you would like to nd the minimum number of one-character changes that allows you do go from a starting words to a target word t, subject to the constraint that whenever you change a character the resulting word has to be in the dictionary. As an example, here's a sequence of one-character changes that allows you to go from the starting word coins to the target word money:
coins
corns
cores
cones
coney
money
Solution:
Lets try to figure out a efficient algorithm to solve the above given algorithm. As per the given problem we have n words of length 5 each, and we would like to find a minimum number of one character changes that allow you to go from a "source word" to a "target word". In order to solve such a problem we can follow the below approach:
- Creating a graph would help us in solving this kind of a problem. Lets consider all n words and each word be a vertex and use these vertices to plot a graph.
- Once we have all the vertices, next we must join all the words that differ by just one character, for example lets consider the words “coins” and “corns” , “dizzy” and “Fizzy” such words differ from each other by a single character. These two words can be joined.
- Given source word S and a target word T we must now identify the vertices between both these words in the graph and now apply a shortest path algorithm to obtain minimum number of one character changes to go from source word to target word.
Below is a part of the graph that can be made out of the n words given.
In the above example we see the words which differ by single character are joined, Now if we consider the source word “COINS” and the target word “MONEY” then the solid line in the example determines the minimum number of one character changes required to go from source word to target word.
We can use the BFS algorithm to calculate the shortest path between source word and target word. This way we will always get an optimal solution as first we are joining words which differ by a single character and then we are calculating the shortest path between two words (Source & Target Words).
Time Complexity Analysis:
Total Time taken = Time to Compare & Join words differing by single character + time taken by BFS algorithm to calculate the shortest path.
= O(N^2 ) + O(|V| + |E|)
~= O(N^2 )
Thereby the algorithm takes O(N^2 ) time to execute.
We can use the BFS algorithm to calculate the shortest path between source word and target word. This way we will always get an optimal solution as first we are joining words which differ by a single character and then we are calculating the shortest path between two words (Source & Target Words).
Time Complexity Analysis:
- Let us know analyse the running time of the above specified algorithm. Here we have considered each of the n words as a separate vertex.
- Now for joining words which differ by only one single character the algorithm will have to compare each word with other, this will take O(N^2 ) time.
- Once the vertices are joined we will now have to find the shortest path between source word and target word using BFS algorithm, The worst case time complexity of BFS algorithm is O(|V| + |E|).
Total Time taken = Time to Compare & Join words differing by single character + time taken by BFS algorithm to calculate the shortest path.
= O(N^2 ) + O(|V| + |E|)
~= O(N^2 )
Thereby the algorithm takes O(N^2 ) time to execute.