Alien Dictionary

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"} --> n words, k chars
Output: Order of characters is 'b', 'd', 'a', 'c'

1. graph of letters, run topSort on the resultant DAG. O(n + k) time, O(n + k) space

- main fn: build graph, then add all directed edges, then run topSort with kahn's algo.

from itertools import tee, izip
from collections import deque

class Graph():
	def __init__(self, numNodes):
		self.nodes = {chr(ord('a')+i):[] for i in range(numNodes)]
	def addEdge(self, char1, char2):
		self.nodes[char1].append(char2)

def getPairs(iterable):
	a, b = tee(iterable)
	b.next()
	return izip(a, b)

# topological sort on graph using kahn's algo
def topSort(g):
	inDegrees = {char:0 for char in g.keys()}
	for char, nbrs in g.items():
		inDegrees[char] = len(nbrs)
	queue = deque()
	ordering = []
	for char, inDegree in inDegrees.items():
		if inDegree == 0:
			queue.append(char)
	while queue:
		char = queue.popleft()
		ordering.append(char)
		for nbrChar in g[char]:
			inDegrees[nbrChar] -= 1
			if inDegrees[nbrChar] == 0:
				queue.append(nbrChar)
	if len(ordering) == len(g):
		return ordering
	else:
		return 'no valid ordering'

def getOrder(words, numChars):
	g = Graph(numChars)
	for edge in getPairs(words):
		g.addEdge(*edge)
	return topSort(g)