Created
June 16, 2016 22:50
-
-
Save jianminchen/85129ed50ce597f896b0f0c5a2fa5586 to your computer and use it in GitHub Desktop.
Leetcode 269 - Alien Dictionary - add more comment, update variable names - look into edge cases 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); | |
} | |
/* | |
* First time to use HashSet UnionWith api - good practice! | |
* | |
*/ | |
public static HashSet<char> getCharSet(string[] words) | |
{ | |
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 | |
* | |
* When the node's inDegree's value goes down to zero, the node | |
* is ready to enqueue. | |
*/ | |
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 node = queue.Peek(); | |
sb.Append(node); | |
queue.Dequeue(); // bug001 - Do not forget to dequeue | |
if (!graph.ContainsKey(node)) | |
break; // something is wrong - "all nodes in the queue are from graph" | |
// check nodes in the dependency list | |
foreach (char runner in graph[node]) | |
{ | |
int index = runner - 'a'; | |
inDegree[index]--; | |
if (inDegree[index] == 0) | |
{ | |
queue.Enqueue(runner); | |
} | |
} | |
} | |
// edge case discussion: | |
// if the graph has cycle, then, ? | |
// What will be case with "" <- give an example: | |
return sb.Length != set.Count ? "" : sb.ToString(); | |
} | |
/* | |
* June 16, 2016 | |
* Work on the detail - How graph is saved 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: ? | |
* | |
* filter out duplicated relationship | |
["za","zb","ca","cb"], then, a->b will show up twice | |
* read Java code for more discussion on this: | |
* http://blog.csdn.net/feliciafay/article/details/50040985 | |
* | |
* Review graph implementation: | |
* http://www.geeksforgeeks.org/graph-and-its-representations/ | |
* | |
* Directed Graph: Edge - From (u) -> To (v) | |
* | |
* Graph setup: | |
* 1. Add node in the graph | |
* 2. update node's dependency list - a HashSet | |
* | |
*/ | |
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]; | |
int shortLength = Math.Min(previous.Length, current.Length); | |
for (int j = 0; j < shortLength; j++) | |
{ | |
char edgeFrom = previous[j]; | |
char edgeTo = current[j]; | |
if (edgeFrom == edgeTo) | |
continue; | |
// start node - need to add a node in the graph | |
if (!graph.ContainsKey(edgeFrom)) { | |
graph.Add(edgeFrom, 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. | |
// filter out duplicated relationship | |
// ["za","zb","ca","cb"], then, a->b will show up twice | |
// | |
// Try to describe what code is doing here: | |
// if adjacency list does not contains edgeTo, then, it is the | |
// first time visited, then, increment one to inDegree array for | |
// the char | |
if (!graph[edgeFrom].Contains(edgeTo)) { | |
inDegree[edgeTo - 'a']++; | |
} | |
// For any case, add edgeTo to the HashSet - first time, add, | |
// second time, will be ignored. | |
// update dependency list. | |
graph[edgeFrom].Add(edgeTo); | |
break; | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment