Back to Problems

Word Ladder

Medium
BFS

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

This is a classic BFS problem where each word is a node, and edges connect words that differ by one letter. BFS finds the shortest path.

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words.

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

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
  • •All the words in wordList are unique
Show Hints (4)
Hint 1: Model this as a graph problem. Each word is a node.
Hint 2: Two nodes are connected if their words differ by exactly one letter.
Hint 3: BFS from beginWord will find the shortest path to endWord.
Hint 4: Use a set for wordList for O(1) lookup. Remove words from the set once visited.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?