In Simple Words: Topological Sort on Directed Acyclic Graph (DAG): 1. Compare adjacent words to find first differing character w1[k] -> w2[k] and add directed edge. 2. In-degree Topological Sort (BFS) or 3-color DFS cycle check. If a cycle is d...

Q90: Alien Dictionary. - DSA Patterns (Multi-Lang)

In Simple Words: Topological Sort on Directed Acyclic Graph (DAG):

Compare adjacent words to find first differing character w1[k] -> w2[k] and add directed edge.
In-degree Topological Sort (BFS) or 3-color DFS cycle check. If a cycle is detected, return "".

Time: $O(C)$ where $C$ is total chars | Space: $O(V + E)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def alienOrder(words: list[str]) -> str:
    adj = {c: set() for w in words for c in w}
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""  # Invalid prefix order
        for j in range(min_len):
            if w1[j] != w2[j]:
                adj[w1[j]].add(w2[j])
                break
    visit = {}  # False = in path, True = visited
    res = []
    def dfs(c):
        if c in visit: return visit[c]
        visit[c] = False
        for nei in adj[c]:
            if not dfs(nei): return False
        visit[c] = True
        res.append(c)
        return True
    for c in adj:
        if not dfs(c): return ""
    return "".join(res[::-1])