Leetcode 269 - Alien dictionary - warm up writing - spend more than 1 hour to write, 5 minutes to fix a bug using debugger - on line 93

Leetcode269_AlienDictionary_warmup.cs

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

namespace _269AlienDictionary_Review
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] words = { "wrt", "wrf", "er", "ett", "rftt" };

            // verify result manually here: "wertf"
            string result = alienOrder(words); 
        }

        public static string alienOrder(string[] words)
        {
            if (words == null || words.Length == 0)
                return "";

            // Graph presentation:
            // nodes, node's dependency list and inDegree array
            // nodes - function getNodes()
            // 
            Dictionary<char, HashSet<char>> dependencyList = new Dictionary<char, HashSet<char>>();

            int[] inDegree = new int[26]; 

            graphSetup(words, dependencyList, inDegree);

            return topoligicalSort(words, dependencyList, inDegree); 
        }

        public static HashSet<char> getNodes(string[] words)
        {
            HashSet<char> hashset = new HashSet<char>();

            foreach (string s in words)
            {
                hashset.UnionWith(s.ToList()); 
            }

            return hashset; 
        }

        /*
         * Motivation talk:
         * set up graph for {"wrt","wrf"}
         * output: 
         * 'f' - add 'f' into dependency list's dictionary, also, update content {'t'}
         * inDegree array setup for inDegree['f'-'a']
         * 
         * two words, at most one edge 
         * 
         * two words, no edge - special case discussion:
         * test case: 
         * case 1: "a", "ab"
         * case 2: 
         * 
         * 
         * That is it! 
         */
        public static void graphSetup(
            string[] words,
            Dictionary<char, HashSet<char>> dependencyList, 
            int[] inDegree
            )
        {
            int len = words.Length;
            if (len == 1)
                return; // cannot do anything 

            for (int i = 1; i < len; i++)
            {
                string prev = words[i - 1];
                string curr = words[i];

                int start = 0;
                while (prev[start] == curr[start])
                {
                    start++; 
                }

                // no edge
                if(start >= Math.Min(prev.Length, curr.Length))
                    return;

                // at most one edge
                char edgeFrom = prev[start];
                //char edgeTo = prev[start];   // bug001 
                char edgeTo = curr[start];

                if (!dependencyList.ContainsKey(edgeFrom))
                {
                    dependencyList.Add(edgeFrom, new HashSet<char>()); 
                }

                if (!dependencyList[edgeFrom].Contains(edgeTo))
                {
                    dependencyList[edgeFrom].Add(edgeTo);
                    inDegree[edgeTo - 'a']++; 
                }               
            }
        }

        /*
         * https://en.wikipedia.org/wiki/Topological_sorting
         * 
         * review the idea of topological sorting:
         * 1. push all indegree nodes with 0 into the queue
         * 2. work on queue, 
         *    step 1: dequeue the node from the queue, 
         *    step 2: update indegree node's value affected - decrement one
         *    step 3: if the dependency list's node indegree value down to zero, 
         *    add the node to the queue
         * 3. construct the output string 
         * 
         * It is just the normal queue process, can you do a bug free writing? 
         */
        public static string topoligicalSort(
            string[]  words, 
            Dictionary<char, HashSet<char>> dependencyList, 
            int[] inDegree
            )
        {
            HashSet<char> nodes = getNodes(words);

            Queue<char> queue = new Queue<char>(); 
            for (int i = 0; i < 26; i++ )
            {
                char runner = (char) ('a' + i);
                if (!nodes.Contains(runner))
                    continue; // skip it! 

                if (inDegree[i] == 0)
                    queue.Enqueue(runner); 
            }

            StringBuilder sb = new StringBuilder(); 
            while (queue.Count > 0)
            {
                char runner = queue.Dequeue();

                sb.Append(runner);
                if (!dependencyList.ContainsKey(runner))
                    continue; 

                HashSet<char> neighbors = dependencyList[runner];
                foreach (char c in neighbors)
                {
                    int index = c - 'a';
                    inDegree[index]--;

                    if (inDegree[index] == 0)
                        queue.Enqueue(c); 
                }
            }

            // edge case: 
            return sb.Length < nodes.Count? "" : sb.ToString(); 
        }

    }
}