5
\$\begingroup\$

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,
\$\endgroup\$
4
\$\begingroup\$
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.

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Is there any specific reason why you used \$\mathcal\$ instead of \$O\$? \$\endgroup\$ – Daniel Dec 25 '17 at 0:53
  • 1
    \$\begingroup\$ @Coal_ Because I like it more \$\endgroup\$ – Graipher Dec 25 '17 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.