Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.
Link: The idea is to create a graph of characters and then find topological sorting of the created graph. Following are the detailed steps.
1) Create a graph g with number of vertices equal to the size of alphabet in the given alien language. For example, if the alphabet size is 5, then there can be 5 characters in words. Initially there are no edges in graph.
2) Do following for every pair of adjacent words in given sorted array.
a) Let the current pair of words be word1 and word2. One by one compare
characters of both words and find the first mismatching characters.
b) Create an edge in g from mismatching character of word1 to that of
word2.
3) Print topological sorting of the above created graph.
import collections
def topological_sort(nodes_map, nodes):
def recursion(nodes_map, node, result, visited):
if node in visited:
return
visited.append(node)
if node in nodes_map:
for c in nodes_map[node]:
recursion(nodes_map, c, result, visited)
result.append(node)
visited, result = [], []
for node in nodes.keys()[::-1]:
recursion(nodes_map, node, result, visited)
return reversed(result)
words = ["baa", "abcd", "abca", "cab", "cad"]
chars = collections.OrderedDict()
for word in words:
for c in word:
chars[c] = True
nodes_map = collections.defaultdict(list)
for i, word in enumerate(words[:-1]):
nxt = words[i+1]
for a, b in zip(word, nxt):
if a != b:
nodes_map[a] += [b]
break
for i in topological_sort(nodes_map, chars):
print i,