noodleProblems/
Word Ladder
#149

Word Ladder

AlgorithmhardHash TableStringBreadth First Search

A **transformation sequence** from beginWord to endWord is a sequence of words begin -> w1 -> w2 -> ... -> end where:

- every adjacent pair of words differs by **exactly one letter**, - every word *after* beginWord is present in wordList (beginWord itself need not be), and - all words have the same length.

Given beginWord, endWord, and the dictionary wordList, return the **number of words** in the *shortest* such transformation sequence (counting both ends). If no transformation sequence exists, return 0.

Example cases

  • five-word ladder
    in beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
    out 5
    hit -> hot -> dot -> dog -> cog has 5 words, and no shorter sequence reaches cog.
  • end word missing
    in beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
    out 0
    cog is not in the dictionary, so no valid sequence can end there.
  • one step
    in beginWord = "a", endWord = "c", wordList = ["a","b","c"]
    out 2
    a -> c differs by one letter and c is in the list — two words.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord, and all words in wordList are unique.
Saved
beginWord =
"hit"
endWord =
"cog"
wordList =
["hot","dot","dog","lot","log","cog"]