Leetcode 269 - Alien Dictionary - warm up practice - 3rd time - a few changes -

Leetcode269_AlienDictionary_Warmup3.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);
        }

        /*
         * Things found in 3rd writing:
         * 1. one spell error topologicalSort function name - topologicalSort not topoligicalSort
         * 2. add nodes variable as part of graph - explicitly add the variable in the graph         * 
         */
        public static string alienOrder(string[] words)
        {
            if (words == null || words.Length <= 1)
                return ""; 

            // Graph prensentation - 3 variables at least 
            // nodes, node's dependency list and inDegree array
            // nodes - function getNodes()
            HashSet<char> nodes = getNodes(words);
            Dictionary<char, HashSet<char>> dependencyList = new Dictionary<char, HashSet<char>>();
            int[] inDegree = new int[26];

            graphSetup(words, dependencyList, inDegree);

            return topologicalSort(words, dependencyList, inDegree, nodes); 
        }

        /*
         * 3rd writing: 
         * look into string.ToList() -> string -> List<char> 
         * try to use HashSet.UnionWith(IEnumerable<T>)
         * 
         * because List<char> should be IEnumerable<T>, T is char here. 
         * 
         */
        public static HashSet<char> getNodes(string[] words)
        {
            HashSet<char> hashset = new HashSet<char>(); 

            foreach(string s in words)
            {
                hashset.UnionWith(s.ToList()); // List<char>
            }

            return hashset; 
        }

        /*
         * Explain the function graphSetup design using the most simple example: 
         * set up graph for {"wrt","wrf"}
         * 
         * Here are the task to complete:
         * 1. Find the first different char - actually, it is an edge in the graph, 
         * here is t-> f
         * 2. Need to handle case - no edge 
         * 3. At most one edge for two consecutive words
         * 4. Only handle the array of string by two neighboring nodes - transmitive 
         * 
         * what to construct in the graph:
         * 1. Add 't' to dependencyList, and also add 't' as char, its neighbors {'f'}, 'f' depends on 't'. 
         * 2. Work on inDegree, increment inDegree['f'-'a']++, 'f' has one more indegree from 't'.
         * 3. need to get the first different char from two strings. 
         * 
         * precondition:
         * words's length >=2 
         * base case <=1 is handled in callee function
         */
        public static void graphSetup(
            string[] words,
            Dictionary<char, HashSet<char>> dependencyList,
            int[] inDegree
            )
        {
            int len = words.Length;

            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))
                    continue;

                // work on style - double checking - using correct variable 
                char edgeFrom = prev[start];
                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']++; 
                }

                // skip if edgeTo is in the hashset. 
            }
        }

        /*
         * Two tasks:
         * 1. get nodes with indegree 0 - enqueue those nodes
         * 2. play with queue
         *    a node is dequeue, append to the output stringBuilder
         *    adjust its dependency list - inDegree value - decrement one
         *    if the neighbor node is with 0 indegree value, push it to the queue
         *   
         * Checking list about queue:
         * 1. First queue is not empty - add nodes into queue first - with indegree 0 nodes
         * 2. when node is dequeued, the indegree is updated accordingly, then, more nodes will be 
         *    added to queue when its indegree is 0
         * 3. Every node in the queue is with indegree 0  - this is a fact.
         */
        public static string topologicalSort(
           string[] words,
           Dictionary<char, HashSet<char>> dependencyList,
           int[] inDegree, 
           HashSet<char> nodes
           )
        {
            //HashSet<char> nodes = getNodes(words); 

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

                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))  // bug001 - forget these 2 lines, runtime execution error 
                    continue; 

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

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

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