# Python Solution with Detailed Explanation

• 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

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):
for ch in w:
if ch not in graph:
graph[ch] = set([])
return

min_length = min(len(w1), len(w2))
found = False
for i in range(min_length):
if w1[i] != 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]
return {}
return graph

def topo_dfs(self, x, g, visited, visiting, st): # Return True if there is a cycle
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)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.