Skip to main content

Word Ladder LeetCode 127

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

  • The first word is beginWord.
  • The last word is endWord.
  • Every adjacent pair of words differs by a single letter.
  • Every intermediate word must be in wordList.

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.

Approach: BFS Level-Order Traversal​

This is a shortest path problem in an implicit graph where:

  • Nodes = Words
  • Edges = Words differing by exactly one letter

BFS Level Expansion​

Answer: 5 (hit → hot → dot → dog → cog)

Algorithm Flow​

Complexity​

  • Time: $O(M^2 \times N)$ where M = word length, N = wordList size
  • Space: $O(M \times N)$ for the visited set

Solution​

public int LadderLength(string beginWord, string endWord, IList<string> wordList)
{
    HashSet<string> wordDict = new HashSet<string>(wordList);
    List<string> visited = new List<string>();
    Queue<string> q = new Queue<string>();
    if (!wordDict.Contains(endWord)) return 0;

    int level = 1;
    q.Enqueue(beginWord);
    while (q.Count != 0)
    {
        int len = q.Count;
        for (int i = 0; i < len; i++)
        {
            var word = q.Dequeue().ToCharArray();
            for (char c = 'a'; c <= 'z'; c = (char)((int)c + 1))
            {
                for (int j = 0; j < beginWord.Length; j++)
                {
                    if (word[j] == c) continue;
                    char temp = word[j];
                    word[j] = c;
                    string newWord = new string(word);
                    if (newWord == endWord) return level + 1;
                    if (wordDict.Contains(newWord) && !visited.Contains(newWord))
                    {
                        visited.Add(newWord);
                        q.Enqueue(newWord);
                    }
                    word[j] = temp;
                }
            }
        }
        level++;
    }

    return 0;
}

Key Insights​

Interview Tips
  • Why BFS? BFS guarantees shortest path in unweighted graphs
  • Optimization: Use HashSet for O(1) word lookup instead of List
  • Bidirectional BFS: Start from both ends for faster convergence (advanced)
Last updated on