NUHMAN.com

Introduction

LeetCode 127: Word Ladder is a classical problem where you are given a beginWord and an endWord, along with a list of valid words. The goal is to find the shortest transformation sequence from beginWord to endWord, where:

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

The problem can be approached efficiently using Breadth-First Search (BFS), as we are essentially finding the shortest path in an unweighted graph, where words are nodes, and an edge exists between two nodes if they differ by exactly one letter.

Problem Statement

Given two words, beginWord and endWord, and a dictionary of words, return the length of the shortest transformation sequence from beginWord to endWord, such that:

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

You may assume that beginWord and endWord are non-empty and that they have the same length.

Example:

go

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

Output: 5

Explanation: The shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.

Approach:

To solve this problem, we will use Breadth-First Search (BFS) to explore the word transformations level by level. Each level corresponds to a transformation from one word to another by changing exactly one letter.

Steps:

1. Preprocessing:

• Convert the list of words into a set for fast lookups.
• If the endWord is not in the dictionary, return 0, as no transformation is possible.

1. BFS Traversal:

• Start from the beginWord and explore all possible valid transformations.
• For each word, generate all its neighbors (words that differ by one character) and add them to the queue if they haven’t been visited yet.
• Keep track of the number of steps taken to reach each word.

1. End Condition:

• As soon as we reach the endWord, return the number of steps taken.
• If no path exists, return 0.

Go Implementation

Solution Using BFS

go

package main

import (
	"fmt"
	"container/queue"
)

func ladderLength(beginWord string, endWord string, wordList []string) int {
	// Create a set of words for quick lookup
	wordSet := make(map[string]bool)
	for _, word := range wordList {
		wordSet[word] = true
	}
	
	// If the endWord is not in the wordSet, return 0
	if _, exists := wordSet[endWord]; !exists {
		return 0
	}
	
	// Initialize BFS queue
	queue := []string{beginWord}
	steps := 1
	
	// Perform BFS
	for len(queue) > 0 {
		// Process each level of the queue
		levelSize := len(queue)
		for i := 0; i < levelSize; i++ {
			currentWord := queue[0]
			queue = queue[1:]

			// Generate all possible next words
			for j := 0; j < len(currentWord); j++ {
				for c := 'a'; c <= 'z'; c++ {
					nextWord := currentWord[:j] + string(c) + currentWord[j+1:]
					if nextWord == endWord {
						return steps + 1
					}
					
					// If the next word is in the wordSet, add it to the queue and mark it as visited
					if wordSet[nextWord] {
						queue = append(queue, nextWord)
						delete(wordSet, nextWord) // Mark as visited
					}
				}
			}
		}
		steps++
	}
	
	// Return 0 if no transformation sequence is found
	return 0
}

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

Explanation:

1. Input Processing:

• We convert the wordList into a map (wordSet) for O(1) time complexity during lookups to check if a word exists in the dictionary.
• If endWord is not present in the wordSet, return 0 because there’s no valid transformation sequence.

1. BFS Traversal:

• Start the BFS from beginWord and explore all possible transformations by changing one letter at a time.
• We generate all possible valid words by changing each letter of the current word and checking if the new word exists in the dictionary.
• For each valid word found, add it to the queue and mark it as visited by deleting it from the wordSet.
• The BFS continues level by level until the endWord is found.

1. End Condition:

• If the endWord is reached, return the number of steps taken so far.
• If the queue is exhausted and no path to the endWord is found, return 0.

Time and Space Complexity

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

Time Complexity:

• BFS Traversal: Each word can generate up to 26 * m possible neighbors (where m is the length of each word). In the worst case, we might explore all n words. Hence, 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.

Space Complexity:

• Queue Storage: We need to store the queue of words being processed in BFS, which can contain up to n words at any point, each of length m. Therefore, the space complexity is O(n * m).
• Word Set: We also store the word list in a set for fast lookups, requiring O(n * m) space.

Edge Cases

1. Edge Case: No Valid Transformation

• Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog"]
• Output: 0
• Explanation: If there is no valid transformation path from beginWord to endWord, the function will return 0.

1. Edge Case: Single Word Transformation

• Input: beginWord = "hit", endWord = "hot", wordList = ["hot"]
• Output: 2
• Explanation: If the beginWord and endWord are only one letter apart, the transformation path will just be beginWord -> endWord.

1. Edge Case: No Valid endWord

• Input: beginWord = "hot", endWord = "cat", wordList = ["dog", "dot", "log"]
• Output: 0
• Explanation: If the endWord does not exist in the dictionary, there can be no valid transformation.

Conclusion

LeetCode 127: Word Ladder is a classic problem that uses Breadth-First Search (BFS) to find the shortest transformation sequence in an unweighted graph. The BFS ensures we explore the shortest paths first, while the use of a set for word lookups ensures efficient checking of valid transformations. The time and space complexity are manageable for most input sizes, making this approach efficient and suitable for solving the problem within the given constraints.