Created
June 16, 2016 19:52
-
-
Save jianminchen/a49496ea21cadcbdda7c1669216c05a5 to your computer and use it in GitHub Desktop.
Leetcode 269 Alien Dictionary - debug the code, work on coding, runs ok with test case: "wrt", "wrf", "er", "ett", "rftt"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace _269AlienDictionary | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
string[] words = { "wrt", "wrf", "er", "ett", "rftt" }; | |
string result = alienOrder(words); | |
} | |
/* | |
* source code from blog: | |
* http://www.cnblogs.com/yrbbest/p/5023584.html | |
* | |
* Topological sorting - Kahn's Algorithm | |
*/ | |
public static String alienOrder(String[] words) { | |
if(words == null || words.Length == 0) { | |
return ""; | |
} | |
Dictionary<char, HashSet<char>> graph = new Dictionary<char, HashSet<char>>(); | |
HashSet<char> set = new HashSet<char>(); | |
foreach (string word in words) { | |
set.UnionWith(word.ToList()); | |
} | |
int[] inDegree = new int[26]; | |
for (int k = 1; k < words.Length; k++) { | |
String previous = words[k - 1]; | |
String current = words[k]; | |
for (int i = 0; i < Math.Min(previous.Length, current.Length); i++) { | |
char preChar = previous[i]; | |
char curChar = current[i]; | |
if (preChar != curChar) { | |
if (!graph.ContainsKey(preChar)) { | |
graph.Add(preChar, new HashSet<char>()); | |
} | |
if (!graph[preChar].Contains(curChar)) { | |
inDegree[curChar - 'a']++; | |
} | |
graph[preChar].Add(curChar); | |
break; | |
} | |
} | |
} | |
// Topological sort - starting from nodes with indegree value 0 | |
// put all those nodes into queue first. | |
Queue<char> queue = new Queue<char>(); | |
for (int i = 0; i < inDegree.Length; i++) { | |
if (inDegree[i] == 0) { | |
char c = (char)('a' + i); | |
if (set.Contains(c)) { | |
queue.Enqueue(c); | |
} | |
} | |
} | |
StringBuilder sb = new StringBuilder(); | |
/* | |
* keep updating indgree value based on the queue's operation | |
* once the node's indegree value's 0, push node to the queue. | |
* That is how it works - continue to output chars | |
*/ | |
while (queue.Count > 0) { | |
char c = queue.Peek(); | |
sb.Append(c); | |
queue.Dequeue(); // bug001 - Do not forget to dequeue | |
if (graph.ContainsKey(c)) { | |
foreach (char runner in graph[c]) { | |
int index = runner - 'a'; | |
inDegree[index]--; | |
if (inDegree[index] == 0) | |
{ | |
queue.Enqueue(runner); | |
} | |
} | |
} | |
} | |
return sb.Length != set.Count ? "" : sb.ToString(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment