Given a sorted dictionary of an alien language, find order of characters

Question

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,

Answer 1

words = ["baa", "abcd", "abca", "cab", "cad"]

I don't believe you ever mutate words so you should make it constant by making it a tuple:

words = ("baa", "abcd", "abca", "cab", "cad")

This:

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,

Should probably wrapped into a "main function". Furthermore, to keep stuff in the "main scope" I highly recomend you actually make a main function. So instead of just:

if __name__ == '__main__':
    words = ("baa", "abcd", "abca", "cab", "cad")
    chars = collections.OrderedDict()
    ...

You should do:

def main():
    words = ("baa", "abcd", "abca", "cab", "cad")
    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,

if __name__ == '__main__':
    main()

Instead of using a list to store results change it to a dequeue by making it results = collection.dequeue(). This gives you the appendleft method which adds stuff to the beginning of the "list". This means you don't need to return reversed(results), just return results.

Answer 2

I would make visited a set, so that if node in visited becomes \$\mathcal{O}(1)\$, instead of \$\mathcal{O}(n)\$. You will also have to replace visited.append(node) with visited.add(node).