NUHMAN.com

Introduction

LeetCode 126: Word Ladder II is an extension of the well-known Word Ladder problem, where the goal is to find all the shortest transformation sequences from a starting word to a target word. Each transformation must change exactly one letter at a time, and each intermediate word must be a valid word from a given dictionary.

In this problem, unlike Word Ladder I, we are required to return all possible shortest transformation sequences, rather than just the length of the shortest sequence. This means we need to explore all potential paths that lead from the start word to the target word while keeping track of the shortest transformations.

The problem can be efficiently solved using Breadth-First Search (BFS) for the shortest path and backtracking to find all possible sequences.

Problem Statement

Given two words, beginWord and endWord, and a dictionary of words, find all shortest transformation sequences from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each transformed word must exist in the given dictionary.

Example:

go

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

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Approach:

To solve the problem, we can break it down into two main steps:

1. BFS to find the shortest path:

• We perform a Breadth-First Search (BFS) starting from the beginWord and explore all possible transformations level by level. During this process, we also build a graph where each word is connected to its neighbors (words that differ by exactly one letter).

1. Backtracking to find all shortest paths:

• Once the BFS completes, we use backtracking to reconstruct all possible paths that lead from the beginWord to the endWord. We ensure that the paths we build are the shortest by stopping backtracking once we reach a node that has already been visited in the BFS at a greater level.

Go Implementation

Solution Using BFS and Backtracking

go

package main

import "fmt"

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
    // Create a set of the wordList for fast lookups
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }
    
    // If endWord is not in wordSet, return an empty result
    if _, exists := wordSet[endWord]; !exists {
        return nil
    }
    
    // BFS to find the shortest path
    level := map[string][]string{beginWord: {}}
    visited := map[string]bool{beginWord: true}
    found := false
    result := [][]string{}
    
    for len(level) > 0 && !found {
        nextLevel := make(map[string][]string)
        for word := range level {
            for i := 0; i < len(word); i++ {
                for c := 'a'; c <= 'z'; c++ {
                    nextWord := word[:i] + string(c) + word[i+1:]
                    if wordSet[nextWord] && !visited[nextWord] {
                        if nextWord == endWord {
                            found = true
                        }
                        nextLevel[nextWord] = append(nextLevel[nextWord], word)
                    }
                }
            }
        }
        
        // Mark visited words in this level
        for word := range nextLevel {
            visited[word] = true
        }
        
        level = nextLevel
    }
    
    // Backtrack to find all shortest paths
    var backtrack func(word string, path []string)
    backtrack = func(word string, path []string) {
        if word == beginWord {
            result = append(result, append([]string{}, append(path, word)...))
            return
        }
        
        for _, prevWord := range level[word] {
            backtrack(prevWord, append(path, word))
        }
    }
    
    // Start backtracking from the endWord
    backtrack(endWord, []string{})
    
    return result
}

func main() {
    beginWord := "hit"
    endWord := "cog"
    wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
    
    result := findLadders(beginWord, endWord, wordList)
    
    fmt.Println(result)
}

Explanation:

1. Input Processing:

• We convert the wordList into a set (wordSet) for O(1) lookup time when checking if a word is valid.
• If the endWord is not in the wordSet, we return an empty result since no valid transformation can be made.

1. BFS (Breadth-First Search):

• We start from the beginWord and explore all words at each level by changing one character at a time.
• For each word, we attempt all possible transformations and check if they are valid words in the dictionary.
• If a word leads to the endWord, we mark it as found and stop the BFS.

1. Backtracking:

• After BFS completes, we backtrack from the endWord to the beginWord, constructing all possible paths.
• The backtracking function starts from the endWord and recursively follows the path to its predecessor nodes, ensuring that all paths are the shortest ones.

1. Result Construction:

• The valid paths are collected in the result slice, and we return it after the backtracking is complete.

Time and Space Complexity

MetricComplexityTime ComplexityO(n * m * 26)Space ComplexityO(n * m)

Time Complexity:

• BFS: Each word can generate up to 26 * m possible neighbors (where m is the length of each word). Thus, the time complexity of BFS is O(n * m * 26), where n is the number of words in the dictionary and m is the length of each word.
• Backtracking: In the worst case, the backtracking process could explore all valid paths, which can be as large as the number of transformations. However, the number of paths is bounded by the shortest transformation sequences, making the complexity of backtracking O(n * m).

Space Complexity:

• BFS: We store the current level and visited nodes, which require O(n * m) space.
• Backtracking: The space complexity for storing the paths is also O(n * m), where n is the number of words and m is the average word length.

Edge Cases

1. Edge Case: No Valid Transformation

• Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog"]
• Output: []
• Explanation: If there is no possible transformation path from beginWord to endWord, we return an empty list.

1. Edge Case: Single Word Path

• Input: beginWord = "hit", endWord = "hot", wordList = ["hot"]
• Output: [["hit", "hot"]]
• Explanation: In the simplest case where beginWord and endWord differ by only one letter, the transformation path consists of just the two words.

1. Edge Case: No Path Found

• Input: beginWord = "hot", endWord = "cog", wordList = ["dog", "lot", "log"]
• Output: []
• Explanation: If there is no valid path, the result will be an empty list.

Conclusion

LeetCode 126: Word Ladder II is a challenging problem that requires efficient graph traversal and backtracking techniques to find all possible shortest transformation sequences. The use of BFS for shortest path discovery and backtracking for path reconstruction ensures that the solution is both optimal and elegant. The algorithm efficiently handles various edge cases, including no valid paths and cases where there is a single-step transformation. The time and space complexities are well within acceptable limits for this type of problem.