Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created June 16, 2016 22:50
Show Gist options
  • Save jianminchen/85129ed50ce597f896b0f0c5a2fa5586 to your computer and use it in GitHub Desktop.
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.
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