Alien Dictionary

Problem: Alien Dictionary

The solution can be divided into 3 parts. The first part reads the dictionary to get an adjacency list to represent a graph shows which letter prior to others. The second part mainly calculates in-degrees of all vertex in graph. The third part uses in-degrees and adjacency list to do topological-sort to get the answer. In addition, we need to maintain an alphabet to store all letters occur since some letters may be missing in the graph due to lack of edge.

Code in Python:

from collections import defaultdict, deque

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        alphabet = ""
        for word in words:
            for c in word:
                if c not in alphabet:
                    alphabet += c

        adj = defaultdict(list)
        for i in xrange(1, len(words)):
            prev, cur = words[i-1], words[i]
            minlen = min(len(prev), len(cur))
            for j in xrange(minlen):
                if prev[j] != cur[j] and cur[j] not in adj[prev[j]]:
                    adj[prev[j]].append(cur[j])
                    break

        indegrees, queue = defaultdict(int), deque([])
        for letter in adj:
            for c in adj[letter]:
                indegrees[c] += 1

        for letter in adj:
            if indegrees[letter] == 0: queue.append(letter)

        ans = ""
        while queue:
            cur = queue.popleft()
            ans += cur
            for letter in adj[cur]:
                indegrees[letter] -= 1
                if indegrees[letter] == 0: queue.append(letter)

        if len(ans) != len(indegrees): return ""

        for c in alphabet:
            if c not in ans:
                ans += c

        return ans