Alien Dictionary

+10

A list of words is sorted in an alphabet you do not know: the 26 lowercase English letters in some secret order. Words compare as usual. The first position where two words differ decides, and when one word is the start of the other, the shorter word comes first.

Return the letters that appear in the words, as one string in alphabet order. When several orders fit, return the one that comes first in ordinary dictionary order. When no order fits, return "invalid".

Function

alienOrder(words: string-array) → string

wordsstring-array: the words, sorted in the unknown alphabet
Returnsstring: the letters in the smallest order that fits, or "invalid"

Constraints

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Every word contains only lowercase English letters.
The same word may appear more than once.

Examples

Input: words = ["tea", "ten", "ate", "act", "cat"]
Output: "etacn"
Explanation: tea before ten puts a before n. The other pairs give t before a, t before c and a before c. No rule mentions e, so the smallest order starts with it: e, t, a, c, n.

Input: words = ["bat", "tab", "tub", "bus"]
Output: "invalid"
Explanation: bat before tab puts b before t, and tub before bus puts t before b. Both cannot hold, so no order fits.

Input: words = ["cooking", "cook"]
Output: "invalid"
Explanation: cook is the start of cooking, so in every alphabet it comes first. The list puts it second, which no order of the letters can explain.

Follow-up

How would you tell whether the fitting order is the only one?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Each pair of neighbouring words gives at most one rule, at the first position where they differ: letter x before letter y. A fitting order is a topological order of those rules. A cycle, or a word placed before its own prefix, makes the list impossible. A min-heap that always places the smallest ready letter gives the smallest order.

Try every order of the letters

Correct, but does not finish on the largest tests

Intuition

Test one arrangement of the k distinct letters by checking each neighbouring pair. At the first differing position the first word's letter must come earlier; with no difference, the first word must not be longer. Walk the arrangements upward from the alphabetical one with next permutation, and the first that passes is the smallest order that fits.

k letters have k! arrangements: 10 give 3,628,800 and 26 give about 4 × 10^26, and each test reads up to 5 × 10^4 characters. When nothing fits, the search tries every one.

Algorithm

Collect the distinct letters and sort them alphabetically.
Record each letter's rank in the current arrangement.
Check every neighbouring pair: at the first differing position the first word's letter needs the smaller rank; with no difference the first word must not be longer.
If every pair passes, return the arrangement; otherwise move to the next larger one.
When there is no next arrangement, return "invalid".

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

Kahn's algorithm with a min-heap

Intuition

In a pair of neighbours only the first difference counts: act before cat says a before c, and the letters after it are never compared. So each pair gives at most one edge.

Kahn's algorithm turns the edges into an order: count each letter's incoming edges, place a letter whose count is 0, remove its outgoing edges, and repeat. A letter on a cycle always keeps an edge from the letter before it on the cycle, so it is never placed. If fewer letters are placed than appear, the answer is "invalid".

Keep the ready letters in a min-heap and place the smallest. Any fitting order starts with a ready letter, so this is the smallest possible first letter, and placing it only removes edges, so it blocks no other letter. In the first example e and t are ready at the start, and e goes first. A plain queue gives a valid order, not always the smallest.

Algorithm

Mark every letter that appears in the words.
For each pair of neighbours, find the first differing position and add the edge between its two letters, once. With no difference and a longer first word, return "invalid".
Count incoming edges and push every marked letter at 0 onto a min-heap.
Pop the smallest letter and append it. Lower the count of each letter it points to, and push any that reach 0.
Return the placed letters if all marked letters were placed, otherwise "invalid".

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

Pitfalls and edge cases

Taking more than one rule from a pair. Reading the second position of act and cat adds c before a, and the first example becomes a false cycle.
Missing the prefix trap. cooking before cook has no differing letter, so a loop that only handles differences returns an order.
Leaving out letters that appear in no rule. In the first example no rule mentions e, yet it belongs in the answer.
Counting a repeated rule twice in the indegree but storing it once. The letter never reaches 0, and a valid list is reported as a cycle.
Treating two equal neighbouring words as the prefix trap; a repeated word is in order.

Frequently asked questions3

What is the time complexity of Alien Dictionary?

O(C + k²), where C is the total number of characters and k ≤ 26 is the number of distinct letters. One pass over the list finds every first difference, and Kahn's algorithm visits at most k² edges. The edge table takes O(k²) space.

Why compare only neighbouring words?

Being sorted is transitive: if every word is at most the next one, the whole list is sorted. So any rule you could read from two distant words already follows from the neighbouring pairs between them.

Why is a word before its own prefix invalid?

In every alphabet a word comes after its own prefix, because the comparison runs out of letters in the shorter word before it finds a difference. It is the one way a list can be impossible without any cycle among its rules.

def alienOrder(words):
    # Write code here

Test #1

Test #2

Test #3

Argument

words = ["tea", "ten", "ate", "act", "cat"]

Expected Output

"etacn"