Taro Logo

Word Ladder

Hard
Meta logo
Meta
Topics:
GraphsStrings

A transformation sequence from word beginWord to word endWord using a dictionary wordList adheres to these rules:

  1. Each adjacent pair of words differs by a single letter.
  2. Every word in the sequence (excluding beginWord) must be in wordList.
  3. The final word in the sequence must equal endWord.

Given beginWord, endWord, and wordList, find the length of the shortest transformation sequence from beginWord to endWord. Return 0 if no such sequence exists.

Example 1:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog"

Example 2:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: endWord is not in wordList.

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • Words consist of lowercase English letters.
  • beginWord != endWord
  • Words in wordList are unique.

Solution


Naive Solution: Brute-Force

The most straightforward approach is to explore all possible transformation sequences from beginWord until we reach endWord. This can be done using a graph-like exploration, where each word in wordList is a node, and edges connect words that differ by only one letter. A brute-force method would involve generating all possible paths and checking their validity.

  1. Build the Graph: Construct a graph where nodes are words, and edges connect words with a single-letter difference.
  2. Explore All Paths: Use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all paths from beginWord to endWord.
  3. Find the Shortest: Keep track of the shortest valid sequence found so far.

Big(O) Analysis:

  • Time Complexity: O(V!), where V is the number of words in wordList. In the worst case, you might explore all possible permutations of words.
  • Space Complexity: O(V), to store the graph and the current path.

This method is highly inefficient and impractical for larger dictionaries due to the exponential time complexity.

Optimal Solution: Breadth-First Search (BFS)

A more efficient approach involves using Breadth-First Search (BFS) to find the shortest transformation sequence. BFS guarantees that the first time we encounter endWord, we've found the shortest path.

  1. Initialization:
    • Create a queue to store words to explore.
    • Initialize the queue with beginWord and a distance of 1.
    • Use a set to keep track of visited words to avoid cycles.
  2. BFS Traversal:
    • While the queue is not empty:
      • Dequeue a word and its distance.
      • For each word in wordList:
        • If the word has not been visited and differs by only one letter from the current word:
          • If the word is endWord, return the current distance + 1.
          • Enqueue the word with the updated distance (distance + 1).
          • Mark the word as visited.
  3. No Path Found:
    • If the queue becomes empty and endWord is not found, return 0.

Big(O) Analysis:

  • Time Complexity: O(M2 * N), where N is the number of words in wordList and M is the length of each word. The M2 comes from checking if two words differ by one letter (M to iterate through the letters, and another M in the worst case of string slicing). We do this for all N words in the worst case.
  • Space Complexity: O(N), for the queue and the visited set, in the worst case, may contain all the words in wordList.

Edge Cases:

  • If endWord is not in wordList, there is no transformation, so return 0.
  • If beginWord is equal to endWord, return 0 (as the problem states beginWord != endWord).
  • If wordList is empty, and beginWord is not endWord, return 0 (no possible transformations).

Code (Python):

from collections import deque

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    if endWord not in wordList:
        return 0

    wordList = set(wordList)
    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        word, distance = queue.popleft()

        if word == endWord:
            return distance

        for i in range(len(word)):
            for char_code in range(ord('a'), ord('z') + 1):
                char = chr(char_code)
                new_word = word[:i] + char + word[i+1:]

                if new_word in wordList and new_word not in visited:
                    queue.append((new_word, distance + 1))
                    visited.add(new_word)

    return 0