Verifying An Alien Dictionary

EASY✓ CHIP-TIMEDLC #953 — FULL STATEMENT ↗

The drill: Words are supposed to be sorted according to some alien alphabet — not a,b,c but a custom 26-letter order. Confirm every adjacent pair in the list respects that ordering, the way ordinary dictionary order works in English.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of words arrives alongside a string that defines a full replacement alphabet — the same 26 letters, just reshuffled into a new order. The task is to confirm the word list is already sorted under that reshuffled order.

Comparison works exactly like ordinary dictionary sorting, just with a different letter ranking: walk two neighboring words character by character, and the first pair of differing letters decides which word comes first under the alien ranking.

When one word runs out of letters before any difference appears, it must be the shorter word and it has to come first — a word that is merely a prefix of the next one is never allowed to sort after it. One violation anywhere in the list fails the whole check.

EX 01

words = ["banana", "ban"] · order = "abcdefghijklmnopqrstuvwxyz"

→ false

PREFIX SHOULD COME FIRST BUT DOESN'T

EX 02

words = ["ban", "banana"] · order = "abcdefghijklmnopqrstuvwxyz"

→ true

PREFIX CORRECTLY COMES FIRST

EX 03

words = ["z", "a"] · order = "zyxwvutsrqponmlkjihgfedcba"

→ true

REVERSED ALIEN ALPHABET, Z SORTS BEFORE A

order string covers all 26 lowercase letters exactly once
word list can run into the thousands, each word fairly short
only adjacent pairs need checking — sorted overall follows from that
a word that's a strict prefix of the next must come first, never after

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

This is exactly dictionary comparison — the only twist is that the alphabet's order isn't a-through-z. What single piece of information would let you compare two letters instantly?

HINT 2 THE STRUCTURE

Build a rank for every letter of the alien alphabet — its position in the order string. Comparing two words is now comparing sequences of ranks instead of letters.

HINT 3 ONE STEP FROM THE ANSWER

Compare each adjacent pair of words rank by rank: the first differing rank decides order; if one word runs out first, it must be the prefix (comes first). If every adjacent pair passes, the whole list is sorted.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE RANK CHECKPATTERN · RANK ARRAY, ONE PASSwords = [cat, bat, apple] · order = "cbadefg...z"

cat

bat

apple

RANK TABLE — LETTER → POSITION

— empty —

STEP 1

order = "cbadefghijklmnopqrstuvwxyz" — a reshuffled alphabet. Build a 26-slot rank table from it once.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/verifying-an-alien-dictionary.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        rank = {c: i for i, c in enumerate(order)}

        def to_ranks(w):
            return [rank[c] for c in w]

        for i in range(len(words) - 1):
            if to_ranks(words[i]) > to_ranks(words[i + 1]):
                return False
        return True

TIME O(N·L)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        def less_or_equal(w1, w2):
            i = 0
            while i < len(w1) and i < len(w2):
                if w1[i] != w2[i]:
                    return order.index(w1[i]) < order.index(w2[i])
                i += 1
            return len(w1) <= len(w2)

        for i in range(len(words) - 1):
            if not less_or_equal(words[i], words[i + 1]):
                return False
        return True

TIME O(N·L·26)SPACE O(1)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] rank = new int[26];
        for (int i = 0; i < order.length(); i++) {
            rank[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < words.length - 1; i++) {
            if (compare(words[i], words[i + 1], rank) > 0) return false;
        }
        return true;
    }

    private int compare(String w1, String w2, int[] rank) {
        int n = Math.min(w1.length(), w2.length());
        for (int i = 0; i < n; i++) {
            int r1 = rank[w1.charAt(i) - 'a'];
            int r2 = rank[w2.charAt(i) - 'a'];
            if (r1 != r2) return r1 - r2;
        }
        return w1.length() - w2.length();
    }
}

TIME O(N·L)SPACE O(1)JAVA · RACE PACE · 22 LN

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 0; i < words.length - 1; i++) {
            if (!lessOrEqual(words[i], words[i + 1], order)) return false;
        }
        return true;
    }

    private boolean lessOrEqual(String w1, String w2, String order) {
        int i = 0;
        while (i < w1.length() && i < w2.length()) {
            char c1 = w1.charAt(i), c2 = w2.charAt(i);
            if (c1 != c2) {
                return order.indexOf(c1) < order.indexOf(c2);
            }
            i++;
        }
        return w1.length() <= w2.length();
    }
}

TIME O(N·L·26)SPACE O(1)JAVA · TRAINING PACE · 20 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED