Skip to main content
CodePeetCodePeet
CodePeet 250

Verifying an Alien Dictionary

EASYProblemSolveExternal Links

Description

You are given a list of words written in an alien language that uses the same 26 lowercase English letters as English, but arranged in a completely different alphabetical order. You are also given a string order that represents the alien alphabet — a permutation of all 26 lowercase letters where the first character has the lowest rank and the last character has the highest rank.

Your task is to determine whether the given list of words is sorted in non-decreasing lexicographic order according to this alien alphabet.

Two words are compared character by character from left to right using the alien order. The first position where the characters differ determines which word comes first — the word whose character has a lower alien rank comes first. If one word is a prefix of another (all characters match up to the shorter word's length), the shorter word is considered smaller and should appear before the longer word.

Examples

Example 1

Input: words = ["hello", "leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

Output: true

Explanation: In this alien alphabet, 'h' is the very first letter (position 0) and 'l' is the second letter (position 1). Since the first characters of the two words are 'h' and 'l' respectively, and 'h' comes before 'l' in the alien order, "hello" is correctly placed before "leetcode". The list is sorted.

Example 2

Input: words = ["word", "world", "row"], order = "worldabcefghijkmnpqstuvxyz"

Output: false

Explanation: Comparing the first pair "word" and "world": the first three characters 'w', 'o', 'r' are identical. At position 3, "word" has 'd' and "world" has 'l'. In the alien order, 'd' is at position 4 while 'l' is at position 3. Since 'd' comes after 'l', "word" is actually greater than "world" in this alien language. The list is not sorted.

Example 3

Input: words = ["apple", "app"], order = "abcdefghijklmnopqrstuvwxyz"

Output: false

Explanation: The first three characters of both words are 'a', 'p', 'p' — identical. However, "apple" is longer than "app", and "app" is a prefix of "apple". In lexicographic ordering, a shorter word that is a prefix of a longer word must come first. Since "apple" (the longer word) appears before "app" (the shorter prefix), the list is not sorted.

Constraints

  • 1 ≤ words.length ≤ 100
  • 1 ≤ words[i].length ≤ 20
  • order.length == 26
  • All characters in words[i] and order are English lowercase letters
  • order is a permutation of all 26 lowercase English letters

Editorial

Brute Force

Intuition

The simplest way to verify that a list is sorted is to check that every pair of elements is in the correct order. If you had a list of numbers, you might compare every number with every other number that comes after it to confirm no inversions exist.

We can apply the same idea here: for every pair of words (i, j) where i < j, verify that words[i] comes before or equals words[j] in the alien dictionary order. If any pair is out of order, the list is not sorted.

To compare two words in the alien order, we scan them character by character from left to right. We first build a mapping from each character to its position in the alien alphabet. Then, for each character position, we compare the alien positions of the two characters. The first position where they differ tells us the ordering. If one word is a prefix of the other and all shared characters match, the shorter word should come first.

This approach is straightforward but performs redundant comparisons — it checks all n×(n−1)/2 pairs even though many of these checks are unnecessary.

Step-by-Step Explanation

Let's trace through with words = ["word", "world", "row"], order = "worldabcefghijkmnpqstuvxyz":

First, build the alien order mapping from the order string:

  • w→0, o→1, r→2, l→3, d→4, a→5, b→6, c→7, e→8, f→9, g→10, h→11, ...

With 3 words, brute force checks all n×(n−1)/2 = 3×2/2 = 3 pairs: (0,1), (0,2), (1,2).

Step 1: Select pair (0, 1): "word" vs "world". Compare character by character.

Step 2: Position 0: 'w' vs 'w'. Alien positions: 0 vs 0. Equal — this character doesn't distinguish the words. Move to the next character.

Step 3: Position 1: 'o' vs 'o'. Alien positions: 1 vs 1. Equal again — still tied. Continue.

Step 4: Position 2: 'r' vs 'r'. Alien positions: 2 vs 2. Equal — the first three characters are identical ('wor'). Continue.

Step 5: Position 3: 'd' vs 'l'. Alien positions: 4 vs 3. The characters finally differ!

Step 6: Since alien position of 'd' (4) is greater than alien position of 'l' (3), 'd' comes AFTER 'l' in the alien alphabet. This means "word" is lexicographically greater than "world" in the alien order.

Step 7: The pair (0, 1) is out of order → return false immediately. The list is not sorted. We don't even need to check the remaining pairs (0,2) and (1,2).

Brute Force — Checking All Pairs for Alien Order — Watch how the brute force approach selects word pairs and compares them character by character using the alien order mapping to determine if the list is sorted.

Algorithm

  1. Build a mapping from each character to its position in the alien order string
  2. For each pair of words (i, j) where 0 ≤ i < j < n:
    a. Compare words[i] and words[j] character by character
    b. For each position k from 0 to min(len(words[i]), len(words[j])) - 1:
    • If the alien position of words[i][k] < words[j][k], the pair is in order — move to the next pair
    • If the alien position of words[i][k] > words[j][k], the pair is out of order — return false
    • If they are equal, continue to the next character position
      c. If all shared characters are equal, check lengths: if words[i] is longer than words[j], the pair is out of order — return false
  3. If all pairs are in order, return true

Code

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        int orderMap[26];
        for (int i = 0; i < 26; i++) {
            orderMap[order[i] - 'a'] = i;
        }
        int n = words.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!isOrdered(words[i], words[j], orderMap)) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    bool isOrdered(const string& w1, const string& w2, int orderMap[]) {
        int len = min(w1.size(), w2.size());
        for (int k = 0; k < len; k++) {
            if (orderMap[w1[k] - 'a'] < orderMap[w2[k] - 'a']) return true;
            if (orderMap[w1[k] - 'a'] > orderMap[w2[k] - 'a']) return false;
        }
        return w1.size() <= w2.size();
    }
};
class Solution:
    def isAlienSorted(self, words: list[str], order: str) -> bool:
        order_map = {c: i for i, c in enumerate(order)}

        def is_ordered(w1: str, w2: str) -> bool:
            for k in range(min(len(w1), len(w2))):
                if order_map[w1[k]] < order_map[w2[k]]:
                    return True
                if order_map[w1[k]] > order_map[w2[k]]:
                    return False
            return len(w1) <= len(w2)

        n = len(words)
        for i in range(n):
            for j in range(i + 1, n):
                if not is_ordered(words[i], words[j]):
                    return False
        return True
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] orderMap = new int[26];
        for (int i = 0; i < 26; i++) {
            orderMap[order.charAt(i) - 'a'] = i;
        }
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!isOrdered(words[i], words[j], orderMap)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isOrdered(String w1, String w2, int[] orderMap) {
        int len = Math.min(w1.length(), w2.length());
        for (int k = 0; k < len; k++) {
            if (orderMap[w1.charAt(k) - 'a'] < orderMap[w2.charAt(k) - 'a']) return true;
            if (orderMap[w1.charAt(k) - 'a'] > orderMap[w2.charAt(k) - 'a']) return false;
        }
        return w1.length() <= w2.length();
    }
}

Complexity Analysis

Time Complexity: O(n² × m)

We check all n×(n−1)/2 pairs of words, which is O(n²) pairs. For each pair, comparing two words character by character takes up to O(m) time, where m is the maximum word length. The order mapping is built in O(26) = O(1) time. Total: O(n² × m).

With the given constraints (n ≤ 100, m ≤ 20), the worst case is about 100 × 99/2 × 20 ≈ 99,000 operations, which is fast enough. But the quadratic growth in the number of words is wasteful.

Space Complexity: O(1)

The order mapping array uses exactly 26 entries regardless of input size — this is constant space. No additional data structures grow with the input.

Why This Approach Is Not Efficient

The brute force checks all n×(n−1)/2 pairs, but many of these comparisons are redundant. The key observation is that lexicographic ordering is transitive: if word A ≤ word B and word B ≤ word C, then word A ≤ word C.

Because of transitivity, we only need to verify that each word is ≤ the word immediately after it. If every consecutive pair is in order, then by transitivity, the entire list must be sorted. This reduces the number of pair comparisons from O(n²) to just n−1.

For n = 100 words:

  • Brute force: 4,950 pair comparisons
  • Adjacent pairs only: 99 pair comparisons

That's a 50× reduction. While both are fast for n ≤ 100, the adjacent-pair approach is algorithmically cleaner and scales much better to larger inputs.

Optimal Approach - Adjacent Pair Comparison

Intuition

Think about how you would verify that a bookshelf is organized alphabetically. You wouldn't compare the first book with every other book, then the second book with every remaining book, and so on. Instead, you would simply scan from left to right, checking that each book comes before or equals the next one. If every consecutive pair is in order, the whole shelf must be sorted.

The same logic applies here. Lexicographic ordering is transitive — if "apple" ≤ "banana" and "banana" ≤ "cherry", then "apple" ≤ "cherry" is guaranteed. So we only need to compare adjacent words.

For each pair of adjacent words, we compare their characters one by one using the alien order. We build a hash map (or array) that maps each character to its position in the alien alphabet, giving us O(1) character rank lookups. At the first differing character, we check whether the alien rank of word1's character is less than word2's. If so, this pair is correctly ordered and we move on. If not, the list is unsorted.

There is one subtle edge case: if one word is a prefix of the next (e.g., "apple" followed by "app"), the longer word should come second. If the shorter word appears after the longer prefix-matching word, the list is not sorted.

Step-by-Step Explanation

Let's trace through with words = ["word", "world", "row"], order = "worldabcefghijkmnpqstuvxyz":

First, build a hash map from each character to its alien position:

  • w→0, o→1, r→2, l→3, d→4, a→5, b→6, c→7, e→8, ...

With 3 words, we only need to compare 2 adjacent pairs: (0,1) and (1,2).

Step 1: Compare adjacent pair (0, 1): "word" vs "world".

Step 2: Position 0: 'w' vs 'w'. Hash map lookup: order['w']=0 and order['w']=0. Equal — the first characters are identical. We cannot determine which word comes first from this character alone. Move to position 1.

Step 3: Position 1: 'o' vs 'o'. order['o']=1 and order['o']=1. Equal — still no distinguishing difference. Continue to position 2.

Step 4: Position 2: 'r' vs 'r'. order['r']=2 and order['r']=2. Equal — the shared prefix 'wor' is identical in both words. The answer must lie in the characters that follow.

Step 5: Position 3: 'd' vs 'l'. order['d']=4 and order['l']=3. Finally, the characters differ!

Step 6: Since 4 > 3, the character 'd' comes AFTER 'l' in the alien alphabet. This means "word" is lexicographically greater than "world" in the alien order, but "word" appears before "world" in the list. This is a violation of sorted order.

Step 7: Return false immediately. We found a violation at the first adjacent pair, so we don't even need to check pair (1,2): "world" vs "row". One violation is enough to prove the list is not sorted.

Adjacent Pair Comparison — Character-by-Character with Alien Order — Watch how we compare adjacent words character by character, using the alien order mapping to determine which character has lower rank, stopping at the first mismatch.

Algorithm

  1. Build a mapping (array or hash map) from each character to its position in the alien order string — this gives O(1) rank lookups
  2. For each pair of adjacent words (i, i+1) where 0 ≤ i < n−1:
    a. Compare words[i] and words[i+1] character by character
    b. For each position k from 0 to min(len(words[i]), len(words[i+1])) − 1:
    • If alien rank of words[i][k] < words[i+1][k], this pair is in order — break and move to the next pair
    • If alien rank of words[i][k] > words[i+1][k], the pair is out of order — return false
    • If equal, continue to the next position
      c. If all shared characters are equal and words[i] is longer than words[i+1], return false (prefix rule)
  3. If all adjacent pairs pass, return true

Code

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        int orderMap[26];
        for (int i = 0; i < 26; i++) {
            orderMap[order[i] - 'a'] = i;
        }
        for (int i = 0; i < (int)words.size() - 1; i++) {
            if (!isOrdered(words[i], words[i + 1], orderMap)) {
                return false;
            }
        }
        return true;
    }

private:
    bool isOrdered(const string& w1, const string& w2, int orderMap[]) {
        int len = min(w1.size(), w2.size());
        for (int k = 0; k < len; k++) {
            if (orderMap[w1[k] - 'a'] < orderMap[w2[k] - 'a']) return true;
            if (orderMap[w1[k] - 'a'] > orderMap[w2[k] - 'a']) return false;
        }
        return w1.size() <= w2.size();
    }
};
class Solution:
    def isAlienSorted(self, words: list[str], order: str) -> bool:
        order_map = {c: i for i, c in enumerate(order)}

        def is_ordered(w1: str, w2: str) -> bool:
            for k in range(min(len(w1), len(w2))):
                if order_map[w1[k]] < order_map[w2[k]]:
                    return True
                if order_map[w1[k]] > order_map[w2[k]]:
                    return False
            return len(w1) <= len(w2)

        for i in range(len(words) - 1):
            if not is_ordered(words[i], words[i + 1]):
                return False
        return True
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] orderMap = new int[26];
        for (int i = 0; i < 26; i++) {
            orderMap[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < words.length - 1; i++) {
            if (!isOrdered(words[i], words[i + 1], orderMap)) {
                return false;
            }
        }
        return true;
    }

    private boolean isOrdered(String w1, String w2, int[] orderMap) {
        int len = Math.min(w1.length(), w2.length());
        for (int k = 0; k < len; k++) {
            if (orderMap[w1.charAt(k) - 'a'] < orderMap[w2.charAt(k) - 'a']) return true;
            if (orderMap[w1.charAt(k) - 'a'] > orderMap[w2.charAt(k) - 'a']) return false;
        }
        return w1.length() <= w2.length();
    }
}

Complexity Analysis

Time Complexity: O(n × m)

We compare n−1 adjacent pairs of words. For each pair, the character-by-character comparison takes up to O(m) time, where m is the maximum word length. Building the order mapping takes O(26) = O(1) time. Total: O(n × m).

More precisely, the total work is proportional to the total number of characters across all words, since each character is compared at most once per adjacent-pair comparison. With n ≤ 100 and m ≤ 20, the worst case is about 99 × 20 = 1,980 character comparisons — extremely efficient.

Space Complexity: O(1)

The order mapping uses a fixed-size array of 26 entries (or a hash map with at most 26 key-value pairs). This does not grow with the input size, so space complexity is constant.