Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time, and each intermediate word must exist in the dictionary.
This one I didn't realize when I started working was in the tree section, and I didn't use any trees to solve it. This solution below is very brute force as a result. A better solution would be to construct a tree based on document distance of each word and use it to find the shortest path.
I'll try that solution out sometime later.
My solution below
- Finds the valid starting words and ending words by seeing which words in the dictionary are within 1 letter different from each
- Takes each of those and bruteforces each letter until a new word in the dictionary is found
- Recurses untill an end word is found or no more possibilities exist
- A list of all solutions is produced
- The shortest one is returned