The hardest part of many BFS problems is seeing the graph at all. Here the nodes are words and two words are adjacent when they differ in exactly one letter; nobody hands you that graph, you generate neighbours as you go.
Given begin_word, end_word and a list word_list, return the number of words in the shortest transformation sequence from begin_word to end_word such that every adjacent pair differs by exactly one letter and every word after the first is in word_list. begin_word itself need not be in the list. Return 0 if no such sequence exists.
Examples
Input: begin_word = "hit", end_word = "cog",
word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: hit -> hot -> dot -> dog -> cog (5 words)
Input: begin_word = "hit", end_word = "cog",
word_list = ["hot", "dot", "dog", "lot", "log"]
Output: 0
Explanation: "cog" is not in the list
Constraints
1 <= len(begin_word) <= 10, all words have the same length, lowercase letters1 <= len(word_list) <= 5000- Target: O(N * L * 26) time where N is the number of words and L their length
Goals
- Run BFS on a graph whose edges are generated on the fly instead of stored
- Count BFS levels to get a shortest path length in an unweighted graph
- Generate neighbours efficiently by mutating one letter at a time