Leetcode: 269. Alien Dictionary

Problem Statement

Understand the problem

Given a sequence of words sorted lexicographically using unknown alphabetic order, return the alphabet's letters sorted in respect to the alphabet's rule.

Devise a plan

Modeling as a graph problem, letters are vertices and an edge (u,v) means that the letter u comes before v in the unknown alphabet. If there are cycles in this graph then there is no way to build (discover) the alphabet because u,v1,v2,...,vk,u means that u comes before u what is impossible. Therefore, this is a Directed Graph. The problem become Pattern: Find topological order of vertices in a graph. Time complexity is O(n) and space complexity is O(n).

Carry out the plan

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        A = {c: [] for w in words for c in w}
        for a, b in zip(words, words[1:]):
            if a == b:
                continue
            if a.startswith(b):
                return ""
            i = 0
            while i < len(a) and i < len(b) and a[i] == b[i]:
                i += 1
            if i < len(a) and i < len(b):
                A[a[i]].append(b[i])
        deg = {c: 0 for c in A}
        for u in A:
            for v in A[u]:
                deg[v] += 1
        queue = [u for u in A if deg[u] == 0]
        ans = []
        for u in queue:
            ans.append(u)
            for v in A[u]:
                deg[v] -= 1
                if deg[v] == 0:
                    queue.append(v)
        if len(ans) != len(A):
            return ""
        return "".join(ans)

from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj = {}
        for w1, w2 in zip(words, words[1:]):
            if len(w2) < len(w1) and w1.startswith(w2):
                return ""
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    adj.setdefault(c1, set())
                    adj[c1].add(c2)
                    break

        NOT_VISITED = "NOT_VISITED"
        OPEN = "OPEN"
        CLOSED = "CLOSED"

        status = {c: NOT_VISITED for w in words for c in w}
        ans = []

        def dfs(u):
            if status[u] == CLOSED:
                return True
            if status[u] == OPEN:
                return False

            status[u] = OPEN
            for v in adj.get(u, []):
                if not dfs(v):
                    return False

            ans.append(u)
            status[u] = CLOSED
            return True

        for c in status:
            if status[c] == NOT_VISITED:
                if not dfs(c):
                    return ""

        return "".join(reversed(ans))

assert Solution().alienOrder(["wrt","wrf","er","ett","rftt"]) == "wertf"
assert Solution().alienOrder(["z","x"]) == "zx"
assert Solution().alienOrder(["z","x","z"]) == ""
assert Solution().alienOrder(["z","z"]) == "z"
assert Solution().alienOrder(["abc","ab"]) == ""

Common mistakes