Given a dictionary of words, a starting word and a target word, we have to find the shortest transformation sequence to reach from the starting word to the target word.
A valid transformation allows forming a new word present in the dictionary by changing only one character.
start = "DOG" target = "CAT" words = ["DOT", "DAT", "CAT", "POT", "PAT"] ans = ['DOG', 'DOT', 'DAT', 'CAT']
We can use BFS to solve this problem.
BFS will guarantee that we always find the shortest path.
1. Start with the starting word.
2. Find all the words that are adjacent to the starting word and put them in a queue.
3. Maintain a parent map to keep track of the parent for the word (as we have to print the path).
4. Dequeue the word from the queue and repeat will the queue is empty or if the target word is found.