Leetcode 126 - word ladder II - convert C++ solution to C# version - blog: http://mrsuyi.com/2016/01/31/leetcode-126/

Leetcode126_wordLadder_Cplusplus_Csharp.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _126WordLadder_Cplusplus_ToCSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            string beginWord = "hit";
            string endWord = "cog";
            string[] arr = new string[5] { "hot", "dot", "dog", "lot", "log" };
            HashSet<string> wordList = new HashSet<string>(arr);

            List<List<string>> result = findLadders(beginWord, endWord, wordList);

        }

        /*
         * 
         * Understand C++ solution, and then, write a C# solution
         * 
         * http://mrsuyi.com/2016/01/31/leetcode-126/
         * 
         * Please write one based on this blog as well 
         * http://blog.csdn.net/kenden23/article/details/17611675
         * 
         */
        public static List<List<string>> findLadders(string beginWord, string endWord, ISet<string> wordList)
        {
            wordList.Add(endWord);

            wordList.Remove(beginWord);

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

            List<List<string>> list = new List<List<string>>(); 
            List<string> list2 = new List<string>(); // ? Figure out better way to do this. 
            list2.Add(beginWord); 
            list.Add(list2); 

            ladders[beginWord] = new List<List<string>>(list); 

            Queue<string> q = new Queue<string>();
            q.Enqueue(beginWord);

            while (q.Count > 0)
            {
                HashSet<string> bfs_nextNodes = new HashSet<string>();

                int cnt = q.Count;

                for (int i = 0; i < cnt; i++)
                {                    
                    char[] arr = q.Peek().ToCharArray();

                    for (int j = 0; j < arr.Length; j++)
                    {
                        char backtracking_char = arr[j];

                        for (char c = 'a'; c <= 'z'; c++)
                        {
                            if (arr[j] == c) continue;                            

                             
                            arr[j] = c;
                            string newstring = new string(arr); //arr.ToString() -> wrong
                            
                            if (wordList.Contains(newstring))
                            {   
                                List<List<string>> newList = new List<List<string>>(); 

                                foreach (List<string> ladder in ladders[q.Peek()])
                                {
                                    List<string> tmpList = new List<string>(ladder);
                                    tmpList.Add(newstring);

                                    newList.Add(tmpList); 
                                }

                                if (!ladders.ContainsKey(newstring))
                                    ladders[newstring] = newList; 
                                else
                                    ladders[newstring].AddRange(newList);   // addRange, save existing ones

                                bfs_nextNodes.Add(new string(arr));  
                            }
                        }

                        arr[j] = backtracking_char;   // backtracking - DFS                       
                    }

                    q.Dequeue();
                }
               
                if (ladders.ContainsKey(endWord))  // ContainsKey, not Contains - Dictionary
                    break; 

                foreach (string s in bfs_nextNodes)
                {
                    wordList.Remove(s);
                    q.Enqueue(s);
                }
            }

            return ladders[endWord];
        }
    }
}