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, v_1, v_2, ..., v_k, 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