Word Ladder hard

Problem Statement

Given two words, beginWord and endWord, and a dictionary's word list wordList, return the shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each intermediate word must exist in the wordList.

If there is no such transformation sequence, return an empty list.

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: ["hit","hot","dot","dog","cog"] Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog" is the shortest transformation sequence.

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Steps

1. Initialization: Add beginWord to a queue queue and a set visited. Create a variable path to track the current path. The path will be a list of lists initially containing [[beginWord]].

2. BFS Traversal: While the queue is not empty:

   • Dequeue the first path from the queue.
   • Get the last word from this path.
   • For each word in wordList:
     • If the word is one edit away from the last word in the current path and is not visited:
       • Create a new path by appending the word to the current path.
       • If the word is endWord, return the new path.
       • Otherwise, add the new path to the queue and mark the word as visited.

3. No Path Found: If the loop completes without finding endWord, return an empty list.

Explanation

The problem is solved using Breadth-First Search (BFS). BFS guarantees finding the shortest path if one exists. We explore all words one edit away from the current word, adding them to the queue. The visited set prevents cycles and redundant exploration. The use of a list of lists to represent the path ensures that we track the entire sequence of transformations.

Code

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return []

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

    while queue:
        path = queue.popleft()
        current_word = path[-1]

        for i in range(len(current_word)):
            for char_code in range(ord('a'), ord('z') + 1):
                new_word = current_word[:i] + chr(char_code) + current_word[i+1:]
                if new_word in word_set and new_word not in visited:
                    new_path = path + [new_word]
                    if new_word == endWord:
                        return new_path
                    queue.append(new_path)
                    visited.add(new_word)
    return []

Complexity

• Time Complexity: O(M * N * 26), where M is the length of the words and N is the length of the wordList. In the worst case, we might explore all possible words (N) and all possible character changes (26) for each position in each word (M).
• Space Complexity: O(M * N), in the worst case, we might store all paths in the queue and visited set. The space used by the path list itself is also linear in the length of the shortest path.