# 269. Alien Dictionary

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.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

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

Output: "" 
Explanation: The order is invalid, so return "".

Note:

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.

# Solution

Approach 1: build pairs of ordering, then find cycles in the graph.

# Code (Python)

Approach 1 (not verified on leetcode):

def derive_order(dictionary):
    
    # build pairs of ordering
    if not dictionary:
        return ''
    pairs = {}
    for i in range(1, len(dictionary)):
        prev_word, word = dictionary[i-1], dictionary[i]
        letter_order = _derive_letter_order(prev_word, word)
        if letter_order:
            prev_letter, next_letter = letter_order
        if prev_letter not in pairs:
            pairs[prev_letter] = []
        pairs[prev_letter].append(next_letter)
    
    # build global ordering
    ordering = []
    visited = {}
    IN_PROGRESS = 0
    FINISHED = 1
    
    # dfs to find cycles
    def dfs(letter):
        if letter in visited and visited[letter] == IN_PROGRESS:
            return False
        if letter not in visited:
            visited[letter] = IN_PROGRESS
            ordering.append(letter)
            if letter in pairs:
                for next_letter in pairs[letter]:
                    if not dfs(next_letter):
                        return False
            visited[letter] = FINISHED
            return True
    
    if dfs(dictionary[0][0]):
        return ''.join(ordering)
    return ''

def _derive_letter_order(word1, word2):
    # assuming word1 != word2 and there's word2 isn't a prefix of word1
    for i in range(min(len(word1), len(word2))):
        if word1[i] != word2[i]:
            return [word1[i], word2[i]]
    return []

test1 = [
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
test2 = [
  "z",
  "x"
]
test3 = [
  "z",
  "x",
  "z"
] 
tests = [test1, test2, test3]
answers = ["wertf", "zx", ""]

for i in range(len(tests)):
    my_answer = derive_order(tests[i])
    print(tests[i], my_answer)
    assert my_answer == answers[i]

# Code (C++)

Approach 1:

Approach 2: