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.1
Input:

[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Eg.2
Input:

[
"z",
"x"
]
Output: "zx"
Eg.3
Input:

[
"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 dictionary
def 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 dictionary
def 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:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store