Alien Dictionary

alien_order.py

"""
Description:
There is a new alien language which uses the latin alphabet. However, the order among
letters are unknown to you. You receive a list of non-empty words from the dictionary,
where words are sorted lexicographically by the rules of this new language. Derive the
order of letters in this language.
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.

Examples:
Input: ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"

Input: ["z", "x"]
Output: "zx"

Input: ["z", "x", "z"] 
Output: "" -- since the input is invalid
"""

from collections import defaultdict

def alienOrder(words):
    """
    :type words: List[str]
    :rtype: str
    """
    pre = defaultdict(set)
    suc = defaultdict(set)
    
    for pair in zip(words, words[1:]):
        for a, b in zip(*pair):
            if a != b:
                suc[a].add(b)
                pre[b].add(a)
                break
    chars = set(''.join(words))
    charToProcess = chars - set(pre)
    order = ''
    while charToProcess:
        ch = charToProcess.pop()
        order += ch
        for b in suc[ch]:
            pre[b].discard(ch)
            if not pre[b]:
                charToProcess.add(b)
    return order if set(order) == chars else ''