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
    }
}

In this program, we have the FindShortestTransformationLength method that takes the beginWord, endWord, and wordList as input and returns the length of the shortest transformation sequence.

First, we create a HashSet called wordSet to store the words in the wordList for constant-time lookup. If the endWord is not in the wordSet, it means the transformation is not possible, and we return 0.

We use a queue, queue, to perform the BFS. We enqueue the beginWord and start the transformation level at 1.

In the while loop, we iterate until the queue is empty. At each level, we process all the words in the queue. For each word, we explore all possible next words by replacing each character with the letters 'a' to 'z', except for the original character. If the transformed word is equal to the endWord, we return the current level plus 1, indicating the length of the shortest transformation sequence.

If the transformed word is in the wordSet, we enqueue it, mark it as visited by removing it from the wordSet, and continue the BFS.

After exploring all words at the current level, we increment the level counter.

If we exhaust all possible transformations without finding the endWord, we return 0, indicating that no transformation sequence exists.

Length of the shortest transformation sequence: 5

The shortest transformation sequence from "hit" to "cog" is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which has a length of 5.