C# solution: Graph BFS


  • 0
    B
    public class Solution 
    {
        public string AlienOrder(string[] words) 
        {
            if (words.Length == 0) return "";
    
            var adjacencyMatrix = new Dictionary<char, HashSet<char>>();
            var inDegrees = new Dictionary<char, int>();
    
            FillOutAdjacencyMatrixAndInDegrees(adjacencyMatrix, inDegrees, words);
    
            var queue = new Queue<char>();
    
            foreach(var keyAndValue in inDegrees)
            {
                if(keyAndValue.Value == 0)
                {
                    queue.Enqueue(keyAndValue.Key);
                }
            }
    
            var result = new List<char>();
    
            while(queue.Any())
            {
                var size =  queue.Count;
    
                for (int s = 0; s < size; s++)
                {
                    var cur = queue.Dequeue();
    
                    result.Add(cur);
    
                    foreach(var next in adjacencyMatrix[cur])
                    {
                        inDegrees[next]--;
    
                        if (inDegrees[next] == 0)
                        {
                            queue.Enqueue(next);
                        }
                    }
                }
            }
    
            if (inDegrees.Values.Any(c=>c != 0)) return "";
    
            return string.Join("", result);
    
        }
    
        private void FillOutAdjacencyMatrixAndInDegrees(Dictionary<char, HashSet<char>> adjacencyMatrix, Dictionary<char, int> inDegrees, string[] words)
        {
            for (int i = 0; i < words.Length; i++)
            {
                for (int j = 0; j < words[i].Length; j++)
                {
                    if (!adjacencyMatrix.ContainsKey(words[i][j]))
                    {
                        var curChar = words[i][j];
                        adjacencyMatrix[curChar] = new HashSet<char>();
                        inDegrees[curChar] = 0;
                    }
                }
            }
    
            for (int j = 0; j < int.MaxValue; j++)
            {
                bool isFinished = true;
                for (int i = 1; i < words.Length; i++)
                {
                    if (j < words[i-1].Length && j < words[i].Length)
                    {
                        isFinished = false;
    
                        var preChar = words[i-1][j];
                        var curChar = words[i][j];
    
                        if (words[i-1].Substring(0, j) == words[i].Substring(0,j))
                        {
                            if (preChar != curChar)
                            {
                                if (!adjacencyMatrix[preChar].Contains(curChar))
                                {
                                    adjacencyMatrix[preChar].Add(curChar);
                                    inDegrees[curChar]++;                               
                                }
                            }
                        }
                    }
                }
    
                if (isFinished) break;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.