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.