Word Ladder hard

Problem Statement

Given two words, beginWord and endWord, and a word list wordList, find the length of the shortest transformation sequence from beginWord to endWord, such that:

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

If no such transformation sequence exists, return 0.

Example 1

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Example 2

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Steps

1. Initialization: Create a HashSet to store the wordList for efficient lookup. Add beginWord to a Queue for breadth-first search (BFS). Initialize a HashSet to track visited words.
2. Breadth-First Search (BFS): While the queue is not empty:
   • Dequeue a word (currentWord).
   • If currentWord is equal to endWord, return the current level (distance).
   • Iterate through all possible one-letter variations of currentWord.
   • For each variation:
     • If the variation exists in the wordList and hasn't been visited:
       • Enqueue the variation.
       • Mark the variation as visited.
3. No Path Found: If the queue becomes empty without finding endWord, return 0.

Explanation

The problem requires finding the shortest path between two words, where each step involves changing only one letter. BFS is the perfect algorithm for this because it explores the graph level by level, guaranteeing that the first time we reach the endWord, we have found the shortest path. The HashSet for visited words prevents cycles and redundant exploration.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        HashSet<string> wordSet = new HashSet<string>(wordList);
        if (!wordSet.Contains(endWord)) return 0;

        Queue<string> queue = new Queue<string>();
        queue.Enqueue(beginWord);
        HashSet<string> visited = new HashSet<string>();
        visited.Add(beginWord);
        int level = 1;

        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                string currentWord = queue.Dequeue();
                if (currentWord == endWord) return level;

                for (int j = 0; j < currentWord.Length; j++) {
                    char[] chars = currentWord.ToCharArray();
                    for (char k = 'a'; k <= 'z'; k++) {
                        chars[j] = k;
                        string newWord = new string(chars);
                        if (wordSet.Contains(newWord) && !visited.Contains(newWord)) {
                            queue.Enqueue(newWord);
                            visited.Add(newWord);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
}

Complexity

• Time Complexity: O(M * N * 26), where M is the length of the words and N is the number of words in the word list. The nested loops iterate through all possible one-letter variations.
• Space Complexity: O(N), where N is the number of words in the word list. The space is dominated by the visited HashSet and the queue. In the worst case, all words could be visited and enqueued.