Graphs Fewest steps with BFS
446. Word Ladder
You are given two words, beginWord and endWord, and a list of words, wordList. All of them have the
same length.
A ladder is a sequence of words that starts with beginWord and ends with endWord. Each word in it
differs from the word before it in exactly one position. Every word after beginWord must be in
wordList; beginWord itself does not have to be.
Return the number of words in the shortest ladder, counting both ends. If no ladder exists, return 0.
Example 1
Input: beginWord = "cold"
endWord = "warm"
wordList = ["cord",
"card",
"ward",
"warm",
"worm",
"corm",
"wore"]
5Explanation: One shortest ladder is cold → cord → card → ward → warm. Another is cold → cord → corm → worm → warm. Both have five words, and no ladder is shorter.
Example 2
Input: beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "lean"]
0Explanation: lead → load → goad comes close, but gold is not in wordList, so no ladder can end there.
Example 3
Input: beginWord = "a"
endWord = "c"
wordList = ["b", "c"]
2Explanation: a and c differ in their only letter, so the ladder is just a → c. beginWord is not in the list, and
that is fine.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ beginWord.length ≤ 10endWord.length == beginWord.length1 ≤ wordList.length ≤ 2 × 104wordList[i].length == beginWord.lengthbeginWord,endWordand everywordList[i]hold only lowercase English letters.beginWord != endWord- The words in
wordListare distinct.
Clarifying questions
What you would ask an interviewer before writing any code.