# Alien Dictionary
https://leetcode.com/problems/alien-dictionary/
## Approach 1: [[bfs|BFS]]
- More about `for-else` at [here](https://docs.python.org/3/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops).
```python
adj = defaultdict(set)
indeg = {c: 0 for word in words for c in word}
# Step 1: Populate adj and indeg
for w1, w2 in zip(words, words[1:]):
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in adj[c1]:
adj[c1].add(c2)
indeg[c2] += 1
break
else: # Check that second word isn't a prefix of first word.
if len(w2) < len(w1):
return ""
# Step 2: We need to repeatedly pick off nodes with an indegree of 0.
output = []
queue = deque([v for v in indeg if not indeg[v]])
while queue:
v = queue.popleft()
output.append(v)
for u in adj[v]:
indeg[u] -= 1
if not indeg[u]:
queue.append(u)
# If not all letters are in output, that means there was a cycle and so
# no valid ordering. Return "" as per the problem description.
if len(output) < len(indeg):
return ""
# Otherwise, convert the ordering we found into a string and return it.
return "".join(output)
```
## Approach 2: [[dfs|DFS]]
- To avoid maintaining a list of vertices with `indeg=0`, use reversed adjacency list instead.
- As a result, we're starting from the nodes without outgoing degree.
- i.e. we have to use [[postorder]] traversal when exploring the graph
- Mark `v` as grey when starting traversal
- If a grey node is encountered, a cycle.
- When finished exploring all children, mark `v` as black. Push it into output.
```python
# Step 0: Put all unique letters into the adj list.
rev_adj = {c: [] for word in words for c in word}
# Step 1: Find all edges and put them in reverse_adj_list.
for w1, w2 in zip(words, words[1:]):
for c1, c2 in zip(w1, w2):
if c1 != c2:
rev_adj[c2].append(c1) # reversed
break # a new word, break it
# Step 2: Depth-first search.
visited = {} # grey = False, black = True
output = []
def dfs(v):
# return False if a cycle is detected
if v in visited:
return visited[v] # black is ok, grey is a cycle, return False
if not all(dfs(w) for w in rev_adj[v]):
return False
visited[v] = True # mark as black
output.append(v)
return True
if not all(dfs(v) for v in rev_adj):
return ""
return "".join(output)
```