PREP36 Editorial

Problem Explanation

You are given two words A and B, and a set W consisting of M words. In one operation you can change a single character of the word, if after that change the resultant word exists in the set W. We have to tell the minimum transformation sequence, or tell if it doesn’t exist.


We can push the endWord and startWord in the wordList for ease for use. We can make an unordered set from the word list to quickly search for words. Now we apply BFS to find the shortest path from the startWord to the endWord. We take a queue that stores the string and the distance to reach that string from the startWord. While the queue is not empty we pop the front element and check for every character change in that string if the resultant string exists in the set. If it does, we erase it from the set and push it in the queue with the incremented distance. We output the distance if we encounter the endWord.