Alien Dictionary

https://leetcode.com/problems/alien-dictionary/

Approach 1: BFS

• More about for-else at here.

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

• 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.

# 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)