Alien Dictionary

LeetCode Premium

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Initial attempt

Time spent: 1h 19m | Runtime: 10.79% | Memory: 56.47%

• My original attempt sliced across each character in the word list to create new, lexicographically relevant words. For example, ['abc', 'adx', 'xyz'] becomes ['aax', 'bd']. This was fine, but it ignored the pathological case of considering length. For example, this is invalid: ['abc', 'ab']. This produced some pretty hacky code that took some time to write.
• I approached this without strictly "knowing" topological sort. I ended up making that up on the fly.

Solution

• Build out lexicographically relevant words based on words. This means forming new words per index in words.
• Build out a graph from those words.
• Find a topological ordering.

One of the tricky bits here is that the input is not guaranteed to valid. There are two places where things can go wrong.

1. The original ordering is impossible due to the length constraint. e.g. ['hi', 'h']
2. There is a cycle in the resultant graph.

Cleaned up code

Time spent: 32m | Runtime: 5.26% | Memory: 80.43%

import collections


class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Build out lexicographically interesting words.
        try:
            lex_words = self.build_lex_words(words)
        except ValueError:
            # This catches the length constraint.
            return ''

        # Build the graph, represented by these two dicts.
        children = collections.defaultdict(set)
        in_degree = collections.defaultdict(int)

        # Used to find starting points for topological sort.
        # Not strictly necessary if we use backtracking.
        not_roots = set()
        nodes = set()
        for word in lex_words:
            first, rest = word[0], word[1:]
            prev = None
            for c in word:
                nodes.add(c)
                if prev is not None:
                    if c not in children[prev]:
                        children[prev].add(c)
                        in_degree[c] += 1
                    not_roots.add(c)
                prev = c

        # Build the ordering.
        result = ''
        roots = nodes - not_roots
        seen = set()
        while roots:
            root = roots.pop()
            seen.add(root)
            result += root
            for child in children[root]:
                if child in seen:
                    return ''
                in_degree[child] -= 1
                if in_degree[child] == 0:
                    roots.add(child)

        return result if len(result) == len(nodes) else ''

    def build_lex_words(self, words):
        prev_letter = None
        lex_word = ''
        batch = None
        result = []
        for word in words:
            if word:
                first, rest = word[0], word[1:]
                if prev_letter != first:
                    lex_word += first
                    prev_letter = first
                    if batch:
                        result.extend(self.build_lex_words(batch))
                    batch = [rest]
                else:
                    batch.append(rest)
            elif prev_letter is not None:
                raise ValueError
        if batch:
            result.extend(self.build_lex_words(batch))
        result.append(lex_word)
        return list(filter(None, result))