Leetcode 126: word ladder II - Fix the bug on line 112

Leetcode126_wordLadder_BFS_AddPathFromStartToCurrent_Line112BugFix.cs

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

namespace _126WordLadder_BFS_AddPahtsFromStartToCurrent
{
    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/
         *  
         * Here is the explanation of design:
         * 
        *             dot -> dog 
        * hit->hot ->            -> cog
        *             lot -> log 
        * so, the queue process is (bredth first search)
        * first  layer: hit
        * second layer: hot
        * third  layer: dot, lot
        * forth  layer: dog, log 
        * fifth  layer: cog
        * 
        * build ladders step by step, from startWord to current. 
        * 
        * Dictionary<string, List<List<string>>> ladders
        * 
        * each string will be the key in ladders
        * hit -> hit
        * hot -> one list, {"hit", "hot"}
        * dot -> one list, {"hit", "hot", "dot"}
        * lot -> one list, {"hit", "hot", "lot"}
        * dog -> one list, {"hit", "hot", "dot", "dog"}
        * log -> one list, {"hit", "hot", "lot", "log"}
        * cog -> two lists, 
        *                  {"hit", "hot", "dot", "dog", "cog"}
        *                  {"hit", "hot", "lot", "log", "cog"}
                
        * Julia made mistakes in writing, because there are 5 levels, 4 loops, and then one if,
        * she got confused the position of code. 
        * So, marks are added in the comment just after the loop - start statement, 
        * and also the closing statement. 
        * 
        */
        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>>>();

            addToDictionaryFirstTime(ladders, beginWord);

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

            while (queue.Count > 0)  // level 1
            {
                /*
                 * test case: hit -> hot->dot->dog->cog
                 *                      ->lot->log
                 *             1      2    3    4   5
                 * five layers:
                 * laye 3: dot, lot both are enqueued
                 */
                HashSet<string> nextHops_BFS = new HashSet<string>();

                int count = queue.Count;

                for (int i = 0; i < count; i++) // level 2
                {
                    // C# char[]  -> string, use new string(char[]), not char[].ToString(). 
                    char[] arr = queue.Peek().ToCharArray();

                    for (int j = 0; j < arr.Length; j++)  //level 3: BFS, all edges by changing one char in string 25 * arr.Length
                    {
                        char backtracking_char = arr[j];

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

                            arr[j] = c;
                            string nextHop = new string(arr);  // newstring -> nextHop 

                            if (wordList.Contains(nextHop)) // level 5:
                            {
                                List<List<string>> newList = new List<List<string>>();

                                foreach (List<string> ladder in ladders[queue.Peek()])
                                {
                                    List<string> tmpList = new List<string>(ladder);
                                    tmpList.Add(nextHop);
                                    newList.Add(tmpList); 
                                }

                                // Same distance, maybe more than 1 list 
                                if (ladders.ContainsKey(nextHop))
                                    ladders[nextHop].AddRange(newList);  // Add api - compile error
                                else
                                    ladders[nextHop] = newList;
                                
                                nextHops_BFS.Add(nextHop); 
                            } // end of level 5
                        } // end of level 4

                        arr[j] = backtracking_char; // backtracking - do not forget. 
                    } // end of level 3 -  end for loop for hop string length

                    queue.Dequeue(); // need to dequeue
                } // end of level 2 -  processing - all nodes in the same distance in the queue

                if (ladders.ContainsKey(endWord))
                break;

                foreach (string s in nextHops_BFS)
                {
                    wordList.Remove(s);
                    queue.Enqueue(s); 
                }
                                
            } // end of level 1 - processing queue - queue.Count > 0

            return ladders[endWord]; 
        }

        /*
         * C# 
         * Add a new entry into the dictionary
         * https://msdn.microsoft.com/en-us/library/9tee9ht2(v=vs.110).aspx
         * Read C# [] operator, Add method
         */
        private static void addToDictionaryFirstTime(Dictionary<string, List<List<string>>> ladders, string word)
        {
            List<List<string>> list = new List<List<string>>();

            List<string> subList = new List<string>();
            subList.Add(word);

            list.Add(subList);

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