Created
June 16, 2016 20:41
-
-
Save jianminchen/47f516b54686080c3a68bc8c3f1d04cb to your computer and use it in GitHub Desktop.
Leetcode 269 Alien Dictionary - add more comment - understand what possible bugs are - where to be careful etc.
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>>(); | |
int AlphabeticSize = 26; | |
int[] inDegree = new int[AlphabeticSize]; | |
graphSetup(words, graph, inDegree); | |
return topologicalSort(words, graph, inDegree); | |
} | |
public static HashSet<char> getCharSet(string[] words) | |
{ | |
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()); | |
} | |
return set; | |
} | |
/* | |
* Topological Sort algorithm in Graph | |
* Need to review | |
* | |
* | |
*/ | |
public static string topologicalSort( | |
string[] words, | |
Dictionary<char, HashSet<char>> graph, | |
int[] inDegree | |
) | |
{ | |
HashSet<char> set = getCharSet(words); | |
int AlphabeticSize = 26; | |
// Topological sort - starting from nodes with indegree value 0 | |
// put all those nodes into queue first. | |
// Go through all 26 chars, and then, add chars with indegree 0 - make | |
// sure that chars are in the HashSet set | |
Queue<char> queue = new Queue<char>(); | |
for (int i = 0; i < AlphabeticSize; i++) | |
{ | |
char curr = (char)('a' + i); | |
if (inDegree[i] == 0 && set.Contains(curr)) | |
{ | |
queue.Enqueue(curr); | |
} | |
} | |
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(); | |
} | |
/* | |
* June 16, 2016 | |
* Work on the detail - How graph is save using dependency list | |
* | |
* Construct the graph | |
* Nodes in the graph at most 26 chars, a, b, c,d, ..., z | |
* | |
* int[] inDegree - 26 | |
* Dictionary<char, HashSet<char>> graph | |
* For example, | |
* "wrt", "wrf", "er", "ett", "rftt" | |
* | |
* inDegree: | |
* 'w' - indegree['w'-'a'] = 0 | |
* "wrt", "wrf" -> we can tell that t->f, so this edge t->f, | |
* how to save it in the graph? | |
* | |
* We choose to save the dependency list -> t has a list of dependency, f is one in the list | |
* graph['t'] is a hashset, and then, make sure that 'f' is added to the hashset | |
* | |
* Next, the smart tip about comparison: | |
* wrt -> wrf, skip first two chars, and then set up third char t->f edge in the graph | |
* You need to figure out what is edge in the graph through this words order. | |
* Extract the information - | |
* | |
* This function is not easy to maintain bug free | |
* Need to enforce some rules in the code: | |
* Rule 1: ? | |
* Rule 2: ? | |
* | |
*/ | |
public static void graphSetup( | |
string[] words, | |
Dictionary<char, HashSet<char>> graph, | |
int[] inDegree) | |
{ | |
for (int i = 1; i < words.Length; i++) { | |
String previous = words[i - 1]; | |
String current = words[i]; | |
for (int j = 0; j < Math.Min(previous.Length, current.Length); j++) { | |
char start = previous[j]; | |
char end = current[j]; | |
if (start == end) | |
continue; | |
// start node - need to add in the graph | |
if (!graph.ContainsKey(start)) { | |
graph.Add(start, new HashSet<char>()); | |
} | |
// Avoid bugs | |
// Do not add same node twice in inDegree array | |
// For example, wrt->wrf => t->f, 'f''s indgree from 't', should not count | |
// twice. | |
if (!graph[start].Contains(end)) { | |
inDegree[end - 'a']++; | |
} | |
graph[start].Add(end); | |
break; | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment