Word Ladder

Naive Solution: Brute-Force

A brute-force approach would involve exploring all possible transformation sequences from the beginWord to the endWord. This could be done using a graph-like traversal, where each word in the wordList is a node, and an edge exists between two words if they differ by only one letter.

1. Build the Graph: Create an adjacency list representing the graph. Iterate through all pairs of words in wordList. If two words differ by only one letter, add an edge between them in the graph.
2. Perform DFS/BFS: Starting from beginWord, perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to find all possible paths to endWord.
3. Find Shortest Path: If endWord is reachable, determine the shortest path among all discovered paths.

Problems with this approach:

• It's highly inefficient, especially for large wordList sizes, because it explores many unnecessary paths.
• The graph construction can be time-consuming.

Big O Runtime: O(V + E) where V is the number of words in the dictionary and E is the number of edges between words.

Big O Space: O(V + E) due to the storage of the graph.

Optimal Solution: Breadth-First Search (BFS)

A more efficient approach uses Breadth-First Search (BFS) to find the shortest transformation sequence. BFS guarantees finding the shortest path in an unweighted graph.

Algorithm:

1. Initialization:
   • Create a queue to store words to visit, starting with beginWord.
   • Create a visited set to keep track of visited words to avoid cycles.
   • Initialize a distance map to store the distance (number of transformations) from beginWord to each word. Set distance[beginWord] = 1.
2. BFS Traversal:
   • While the queue is not empty:
     • Dequeue a word currentWord.
     • If currentWord is equal to endWord, return distance[currentWord].
     • Generate all possible one-letter variations of currentWord.
     • For each variation:
       • If the variation is in wordList and has not been visited:
         • Enqueue the variation.
         • Mark the variation as visited.
         • Set distance[variation] = distance[currentWord] + 1.
3. No Path Found: If the queue becomes empty and endWord is not reached, return 0.

Big O Runtime: O(M^2 * N), where N is the number of words in wordList and M is the length of each word.

Big O Space: O(M * N), where N is the number of words in wordList and M is the length of each word.

Edge Cases:

• If endWord is not in wordList, there is no transformation sequence, return 0.
• If beginWord and endWord are the same, return 0 if the wordList doesn't have the beginWord or 1 if the wordList contains the beginWord.
• If wordList is empty, return 0.

from collections import deque

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

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

    while queue:
        word, length = queue.popleft()
        if word == endWord:
            return length

        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 wordSet and new_word not in visited:
                    queue.append((new_word, length + 1))
                    visited.add(new_word)

    return 0