{x}
blog image

Word Ladder

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.

 

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 long.

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.

127. Word Ladder

This problem asks for the length of the shortest transformation sequence from beginWord to endWord using words from wordList, where each step involves changing only one letter.

Solution 1: Breadth-First Search (BFS)

This solution uses Breadth-First Search (BFS) to find the shortest transformation sequence. BFS guarantees that the first time we reach endWord, we've found the shortest path.

Algorithm:

  1. Initialization: Create a queue q initialized with beginWord, a set words containing all words from wordList, and a counter ans initialized to 1 (representing the length of the sequence starting with beginWord).

  2. Iteration: While the queue is not empty:

    • Increment ans (each iteration represents one step deeper in the transformation).
    • Process all words currently in the queue:
      • For each word, generate all possible one-letter-different words:
        • If the generated word is in words and is the endWord, return ans.
        • If the generated word is in words and hasn't been visited, add it to the queue and remove it from words (to avoid cycles).
  3. No Path: If the queue becomes empty without finding endWord, it means there's no transformation sequence, so return 0.

Time Complexity: O(MNL), where M is the length of wordList, N is the length of each word, and L is the length of the alphabet (26). In the worst case, we might explore all possible variations of all words.

Space Complexity: O(M*N) in the worst case. The space is dominated by the queue and the words set.

Code (Python):

from collections import deque
 
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        q = deque([beginWord])
        ans = 1
        while q:
            ans += 1
            for _ in range(len(q)):
                s = q.popleft()
                s = list(s)
                for i in range(len(s)):
                    ch = s[i]
                    for j in range(26):
                        s[i] = chr(ord('a') + j)
                        t = ''.join(s)
                        if t not in words:
                            continue
                        if t == endWord:
                            return ans
                        q.append(t)
                        words.remove(t)  # Avoid cycles
                    s[i] = ch  # Restore original character
        return 0

Similar implementations exist in Java, C++, Go, and TypeScript, reflecting the same algorithm.

Solution 2: Bidirectional BFS

Bidirectional BFS optimizes the search by running two BFS searches simultaneously—one from beginWord and one from endWord. This reduces the search space, often significantly improving performance.

Algorithm:

  1. Initialization: Two queues, q1 (from beginWord) and q2 (from endWord), are created, along with two maps, m1 and m2, tracking distances from the starting points.

  2. Iteration: The algorithm prioritizes expanding the smaller queue in each iteration. It checks for intersections between the queues. If a word is found in both queues, the shortest path has been found.

  3. Termination: The search ends when either a path is found (intersection) or one of the queues becomes empty (no path).

Time Complexity: O(MN2^L), where M is the length of wordList, N is the length of words, and L is average word length. While still exponential in the worst case, it tends to be significantly faster than unidirectional BFS.

Space Complexity: O(M*N) in the worst case (due to the queues and maps)

Code (Python):

from collections import deque
 
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words: return 0  # Optimization: Early exit if endWord isn't in wordList
 
        q1, q2 = deque([beginWord]), deque([endWord])
        m1, m2 = {beginWord: 0}, {endWord: 0}
 
        while q1 and q2:
            if len(q1) <= len(q2):
                res = self._extend(m1, m2, q1, words)
            else:
                res = self._extend(m2, m1, q2, words)
 
            if res != -1:
                return res + 1
        return 0
 
    def _extend(self, m1, m2, q, words):
        for _ in range(len(q)):
            s = q.popleft()
            step = m1[s]
            s_list = list(s)
            for i in range(len(s_list)):
                ch = s_list[i]
                for j in range(26):
                    s_list[i] = chr(ord('a') + j)
                    t = "".join(s_list)
                    if t in m1 or t not in words: continue
                    if t in m2: return step + 1 + m2[t]
                    m1[t] = step + 1
                    q.append(t)
                s_list[i] = ch
        return -1
 

Again, comparable implementations can be written for other languages. The core bidirectional BFS strategy remains consistent. Note that while the worst-case complexity remains high, bidirectional BFS often offers a substantial performance advantage in practice.