**Solution**

**Alien Dictionary** https://leetcode.com/problems/alien-dictionary/

**Topological Sort Based Solution**

**Synoposis**

- The basic idea behind this problem is simple. Build a graph from the dictionary of words. Then do a topological sort of the words. The meat is in the details and corner cases.

**Meaning of Lexicographically Smaller**

- Understanding
**what lexicographically smaller really means**. Notice that adjacent words in the dictionary dictate the order. Letters within the word do not determine the lexicographic order. https://discuss.leetcode.com/topic/22395/the-description-is-wrong

**Building an Input Graph**

- Graph is a dictionary with key as character and edge end points as a set
- Every adjacent pair of word is extracted. All their characters are added to a graph as keys
- Now every adjacent character is compared. The first non-matching character determines a relationship u -> v and is added to graph. We break at this point since the remainder mis-matches do not imply any relationship.
- Notice a pair like ("wrtkj","wrt") - > this indicates no relationship since wrt match and then the smaller word is actually longer length than bigger word. This needs to be reported as an error.
- build_graph method returns the graph. If an error is found, empty graph is returned.

**Topological Sort**

- DFS or BFS can be used to implement topological sort. We use DFS.
- We run topological sort on each vertex.
- Topological sort requires a directed acyclic graph. If there is a cycle, we return True.
- How do we detect a cycle? We use the concept of back-edges. We maintain a visiting and visited array.
- Topological sort can be implemented using BFS as well. https://www.youtube.com/watch?v=71eHuQvSwc0

**Interesting Examples**

- ["wrtkj","wrt"] # Incorrect input
- ["a","b","a"] # Cycle
- ["wnlb"]

```
class Solution(object):
def add_vertices(self, w, graph):
for ch in w:
if ch not in graph:
graph[ch] = set([])
return
def add_words_to_graph(self, graph, w1, w2):
self.add_vertices(w1, graph)
self.add_vertices(w2, graph)
min_length = min(len(w1), len(w2))
found = False
for i in range(min_length):
if w1[i] != w2[i]:
graph[w1[i]].add(w2[i])
found = True
break
if found == False and len(w1) > len(w2):
return False # "abstract", "abs" is an error. But "abs", "abstract" is perfectly fine.
return True
def build_graph(self, words):
graph = {}
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if not self.add_words_to_graph(graph, w1, w2):
return {}
self.add_vertices(words[-1], graph)
return graph
def topo_dfs(self, x, g, visited, visiting, st): # Return True if there is a cycle
visited.add(x)
visiting.add(x)
for nbr in g[x]:
if nbr in visiting: # Back-Edge!
return True
if nbr not in visited:
if self.topo_dfs(nbr, g, visited, visiting, st):
return True
visiting.remove(x)
st.append(x)
return False
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
if words == []:
return ""
graph = self.build_graph(words)
visited, visiting, st = set([]), set([]), []
for k in graph.keys():
if k not in visited:
if self.topo_dfs(k, graph, visited, visiting, st):
return ""
st.reverse()
return "".join(st)
```