using System;

using System.Collections.Generic;           

​

public class Program

{

    public static void Main()

    {

        string beginWord = "hit";

        string endWord = "cog";

        List<string> wordList = new List<string>(){ "hot", "dot", "dog", "lot", "log", "cog" }; 

        Console.Write(LadderLength(beginWord, endWord, wordList));

    }

    public static int LadderLength(string beginWord, string endWord, IList<string> wordList)

        {

            wordList.Add(beginWord);

​

            Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();

            foreach (var word in wordList)

            {

                for (int i = 0; i < word.Length; i++)

                {

                    var key = word.Substring(0, i) + '*' + word.Substring(i + 1);

                    if (!map.ContainsKey(key))

                        map.Add(key, new List<string>());

​

                    map[key].Add(word);

                }

            }

​

            Queue<(string, int)> Q = new Queue<(string, int)>();

​

            Dictionary<string, bool> visited = new Dictionary<string, bool>();

​

            visited.Add(beginWord, true);

​

            Q.Enqueue((beginWord, 1));

​

            while (Q.Count > 0)

            {

                var val = Q.Dequeue();

                var wordCurr = val.Item1;

                var level = val.Item2;

​

                for (int i = 0; i < wordCurr.Length; i++)

                {

                    string newKey = wordCurr.Substring(0, i) + '*' + wordCurr.Substring(i + 1);

                    var lst = map[newKey];

                    foreach (var item in map[newKey])

                    {

                        if (item == endWord)

                            return level + 1;

​

                        if (item != wordCurr)

                        {

                            if (!visited.ContainsKey(item))

                            {

                                visited.Add(item, true);

                                Q.Enqueue((item, level + 1));

                            }

​

                        }

                    }

                }

            }

​

​

            return 0;

        }

}