Verifying an Alien Dictionary

Easy
513.

Verifying an Alien Dictionary

Verifying an Alien Dictionary is an easy coding problem on arrays, strings and hash table, asked in Amazon, Google and Meta interviews.

An alien language uses the English letters but in a different alphabetical order, given by the permutation order.

Return true if words is sorted lexicographically according to that order.

Example 1

Input
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output
true
Explanation
h precedes l in this alphabet.

Example 2

Input
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output
false
Explanation
"word" comes after "world" because d follows l here.

Example 3

Input
words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output
false
Explanation
A prefix must come before the longer word.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • order.length == 26
  • All characters are lowercase English letters and order is a permutation of them.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Verifying an Alien Dictionary — Problem & Solution

Verifying an Alien Dictionary solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Verifying an Alien Dictionary is an easy coding problem on arrays, strings and hash table, asked in Amazon, Google and Meta interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Hash Table
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An alien language uses the English letters but in a different alphabetical order, given by the permutation order.

Return true if words is sorted lexicographically according to that order.

Example 1

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: h precedes l in this alphabet.

Example 2

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: "word" comes after "world" because d follows l here.

Example 3

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: A prefix must come before the longer word.

Constraints

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

Hints for Verifying an Alien Dictionary

  1. Hint 1

    Turn the alphabet string into a rank lookup: rank[c] is the position of c in order.

  2. Hint 2

    Comparing two words means finding the first index where they differ and comparing ranks there.

  3. Hint 3

    If neither differs before one ends, the shorter word must come first.

How to solve Verifying an Alien Dictionary

Re-mapping each letter to its rank in the alien alphabet reduces the problem to ordinary lexicographic comparison of adjacent word pairs.

Approach

  1. Build rank from order, mapping each letter to its index.
  2. For each adjacent pair (a, b), scan to the first position where they differ.
  3. If such a position exists, the pair is in order iff rank[a[i]] < rank[b[i]].
  4. If no position differs, the pair is in order iff a.length <= b.length.
  5. Return false on the first violation, true otherwise.

Why it works

Lexicographic order is a total order, so checking only adjacent pairs is sufficient — sortedness is a chain of pairwise comparisons.

Complexity

  • Time — O(total characters)
  • Space — O(1) — the rank table is 26 entries

Pitfalls

  • Missing the prefix rule marks ["apple","app"] as sorted.
  • Comparing the raw strings with the language's built-in comparison ignores order entirely.
  • Comparing all pairs instead of adjacent ones is O(n²) for no benefit.

Reference solution

Python

from typing import List

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

    def le(a, b):
        for x, y in zip(a, b):
            if x != y:
                return rank[x] < rank[y]
        return len(a) <= len(b)

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

Java

public static 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 w = 0; w + 1 < words.length; w++) {
        String a = words[w], b = words[w + 1];
        int n = Math.min(a.length(), b.length());
        boolean decided = false;
        for (int i = 0; i < n; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                if (rank[a.charAt(i) - 'a'] > rank[b.charAt(i) - 'a']) return false;
                decided = true;
                break;
            }
        }
        if (!decided && a.length() > b.length()) return false;
    }
    return true;
}

C++

bool isAlienSorted(vector<string>& words, string order) {
    int rank[26];
    for (int i = 0; i < (int) order.size(); i++) rank[order[i] - 'a'] = i;
    for (int w = 0; w + 1 < (int) words.size(); w++) {
        const string& a = words[w];
        const string& b = words[w + 1];
        int n = (int) min(a.size(), b.size());
        bool decided = false;
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) {
                if (rank[a[i] - 'a'] > rank[b[i] - 'a']) return false;
                decided = true;
                break;
            }
        }
        if (!decided && a.size() > b.size()) return false;
    }
    return true;
}

JavaScript

var isAlienSorted = function(words, order) {
    const rank = {};
    for (let i = 0; i < order.length; i++) rank[order.charAt(i)] = i;
    function le(a, b) {
        const n = Math.min(a.length, b.length);
        for (let i = 0; i < n; i++) {
            if (a.charAt(i) !== b.charAt(i)) return rank[a.charAt(i)] < rank[b.charAt(i)];
        }
        return a.length <= b.length;
    }
    for (let i = 0; i + 1 < words.length; i++) {
        if (!le(words[i], words[i + 1])) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings