# Graph (Topological Sort)

• 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.Eg.1Input:[  "wrt",  "wrf",  "er",  "ett",  "rftt"]Output: "wertf"Eg.2Input:[  "z",  "x"]Output: "zx"Eg.3Input:[  "z",  "x",  "z"] Output: "" Explanation: The order is invalid, so return "".Note:- You may assume all letters are in lowercase.- If the order is invalid, return an empty string.- There may be multiple valid order of letters, return any one of them is fine.`
• Code:
`# Time O(P), P = no. of chars to compare in order to create the dictionary# Space O(V+E) for dictionarydef create_dict():    chars = set(''.join(words))    g_dict = {char: [] for char in chars}    reverse_dict = {char: [] for char in chars}    for w1, w2 in zip(words, words[1:]):        if len(w1) > len(w2) and w1[:len(w2)] == w2:            return {}, {}        for char1, char2 in zip(w1, w2):            if char1 != char2:                if char2 not in g_dict[char1]:                    g_dict[char1].append(char2)                    reverse_dict[char2].append(char1)                break    return g_dict, reverse_dict`
`# Time O(V+E)# Space O(V+E), for dictionarydef topological_sort(g_dict, reverse_dict):    todo = collections.deque([k for k, v in reverse_dict.items() if not v])    result = ''    while todo:        node = todo.popleft()        result += str(node)        for next_node in g_dict[node]:            reverse_dict[next_node].remove(node)            if not reverse_dict[next_node]:                todo.append(next_node)    if len(result) < len(reverse_dict):        return ''    return result`
`# Time O(P), P = no. of chars in all input string# Space O(V+E), for dictionary. Since dictionary only has 26 keys, relations maximum is 26^2. It's O(1). N = total lenght of all words. so O(V+min(V^2, N))def alienOrder(self, words: List[str]) -> str:    def create_dict():        ...    def topological_sort(g_dict, reverse_dict):        ...    if not words: return ''    g_dict, reverse_dict = create_dict()    if g_dict == {}: return ''    return topological_sort(g_dict, reverse_dict)`
• Other questions related to topological sort:

--

--