C# program to Given two words, beginWord and endWord, and a word list, find the length of the shortest transformation sequence from beginWord to endWord.

To solve the problem of finding the length of the shortest transformation sequence from a given beginWord to endWord using a word list, you can apply the Breadth-First Search (BFS) algorithm. Here's a C# program that accomplishes this task:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        string beginWord = "hit";
        string endWord = "cog";
        List wordList = new List() { "hot", "dot", "dog", "lot", "log", "cog" };

        int shortestLength = FindShortestTransformationLength(beginWord, endWord, wordList);

        Console.WriteLine("Length of the shortest transformation sequence: " + shortestLength);
    }

    static int FindShortestTransformationLength(string beginWord, string endWord, List wordList)
    {
        // Create a hash set for constant-time lookup of words
        HashSet wordSet = new HashSet(wordList);

        if (!wordSet.Contains(endWord))
        {
            return 0; // End word is not in the word list, transformation is not possible
        }

        Queue queue = new Queue();
        queue.Enqueue(beginWord);

        int level = 1; // Transformation level
        while (queue.Count > 0)
        {
            int size = queue.Count;
            for (int i = 0; i < size; i++)
            {
                string currentWord = queue.Dequeue();

                // Explore all possible next words by replacing each character
                char[] charArray = currentWord.ToCharArray();
                for (int j = 0; j < charArray.Length; j++)
                {
                    char originalChar = charArray[j];
                    for (char c = 'a'; c <= 'z'; c++)
                    {
                        if (c == originalChar)
                        {
                            continue; // Skip the same character
                        }

                        charArray[j] = c;
                        string transformedWord = new string(charArray);

                        if (transformedWord == endWord)
                        {
                            return level + 1; // Transformation sequence found
                        }

                        if (wordSet.Contains(transformedWord))
                        {
                            queue.Enqueue(transformedWord);
                            wordSet.Remove(transformedWord); // Mark the word as visited
                        }
                    }
                    charArray[j] = originalChar; // Revert the character back
                }
            }
            level++;
        }

        return 0; // No transformation sequence found
    }
}

Explanation of Word Ladder C# Code

This C# program is designed to find the shortest transformation sequence from a beginWord to an endWord by changing one letter at a time. Each intermediate word in the sequence must exist in a given wordList. This problem is often referred to as the Word Ladder problem. Below is a detailed explanation of the code:

1. Program Overview

• The program starts with a beginWord (e.g., "hit") and an endWord (e.g., "cog").
• A list of valid words (wordList) is provided, which includes all possible intermediate words that can be used in the transformation sequence.
• The goal is to find the shortest sequence of transformations from beginWord to endWord, where each transformation changes one letter at a time, and each intermediate word must exist in wordList.

2. Main Method

• The Main method initializes the beginWord, endWord, and wordList.
• It calls the FindShortestTransformationLength method to compute the length of the shortest transformation sequence.
• The result is printed to the console.

3. FindShortestTransformationLength Method

This method implements a Breadth-First Search (BFS) algorithm to find the shortest transformation sequence. Here's how it works:

Step 1: Setup

• A HashSet named wordSet is created from the wordList for constant-time lookup of words.
• If the endWord is not in the wordSet, the transformation is impossible, and the method immediately returns 0.

Step 2: BFS Initialization

• A Queue is used to facilitate the BFS. The beginWord is added to the queue.
• A variable level is initialized to 1 to keep track of the number of transformations (levels) in the BFS.

Step 3: BFS Execution

• The BFS loop runs as long as there are words in the queue.
• For each word in the queue:
  • The word is dequeued (currentWord).
  • Each character in currentWord is replaced with every possible letter from 'a' to 'z' to generate all possible transformations.
  • If a transformation matches the endWord, the method returns level + 1 (the length of the shortest transformation sequence).
  • If a transformation exists in the wordSet, it is added to the queue, and the word is removed from the wordSet to mark it as visited (preventing reprocessing).
  • The character is reverted to its original state before moving to the next character.

Step 4: Level Increment

• After processing all words at the current level, the level is incremented to move to the next level of transformations.

Step 5: Termination

• If the queue is exhausted and no transformation sequence is found, the method returns 0.

4. Example Walkthrough

Let’s walk through the example provided in the code:

Input

beginWord = "hit"
endWord = "cog"
wordList = { "hot", "dot", "dog", "lot", "log", "cog" }

BFS Execution

1. Level 1:
   • Start with "hit".
   • Transformations:
     • "hit" → "hot" (valid, added to queue).
   • Queue: ["hot"].
2. Level 2:
   • Process "hot".
   • Transformations:
     • "hot" → "dot" (valid, added to queue).
     • "hot" → "lot" (valid, added to queue).
   • Queue: ["dot", "lot"].
3. Level 3:
   • Process "dot".
   • Transformations:
     • "dot" → "dog" (valid, added to queue).
   • Process "lot".
   • Transformations:
     • "lot" → "log" (valid, added to queue).
   • Queue: ["dog", "log"].
4. Level 4:
   • Process "dog".
   • Transformations:
     • "dog" → "cog" (matches endWord, return level + 1 = 5).

5. Key Points

• Breadth-First Search (BFS) is used because it guarantees the shortest path in an unweighted graph (each transformation is considered a step).
• The HashSet ensures efficient lookup and marking of visited words.
• Each transformation involves replacing one character at a time and checking if the new word exists in the wordList.
• The program handles edge cases, such as when the endWord is not in the wordList.

6. Output

For the given input, the program outputs:

Length of the shortest transformation sequence: 5

7. Code Summary

• The program efficiently finds the shortest transformation sequence using BFS.
• It ensures that each intermediate word is valid and avoids reprocessing by marking words as visited.
• The algorithm is robust and handles edge cases gracefully.