How to Verify Alien Dictionary Order Efficiently (LeetCode 953)

The article begins with a light‑hearted compilation of Chinese companies that offered unusually large year‑end bonuses, citing data from the professional networking platform Maimai.

It then turns to a technical discussion of LeetCode problem 953 “Alien Dictionary”. The problem asks whether an array of words is sorted according to a given custom order of the 26 lowercase English letters. Two solution strategies are presented:

Full‑array sorting approach

A copy of the original words array is made, then Arrays.sort is invoked with a comparator that maps each character to its rank using an int[26] array built from the order string. After sorting, the method compares the sorted clone with the original array; any mismatch returns false, otherwise true.

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] ord = new int[26];
        for (int i = 0; i < 26; i++) ord[order.charAt(i) - 'a'] = i;
        String[] clone = words.clone();
        Arrays.sort(clone, (a, b) -> {
            int n = a.length(), m = b.length();
            int i = 0, j = 0;
            while (i < n && j < m) {
                int c1 = a.charAt(i) - 'a', c2 = b.charAt(j) - 'a';
                if (c1 != c2) return ord[c1] - ord[c2];
                i++; j++;
            }
            if (i < n) return 1;
            if (j < m) return -1;
            return 0;
        });
        for (int i = 0; i < words.length; i++) {
            if (!clone[i].equals(words[i])) return false;
        }
        return true;
    }
}

Optimized pairwise comparison

To avoid sorting the whole array, a helper check method directly compares two adjacent words using the same rank array. The main loop iterates from the second word onward, calling check(words[i‑1], words[i]); a positive result indicates the order is violated and the method returns false. If all adjacent pairs are in order, it returns true.

class Solution {
    int[] ord = new int[26];
    int check(String a, String b) {
        int n = a.length(), m = b.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            int c1 = a.charAt(i) - 'a', c2 = b.charAt(j) - 'a';
            if (c1 != c2) return ord[c1] - ord[c2];
            i++; j++;
        }
        if (i < n) return 1;
        if (j < m) return -1;
        return 0;
    }
    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 0; i < 26; i++) ord[order.charAt(i) - 'a'] = i;
        int n = words.length;
        for (int i = 1; i < n; i++) {
            if (check(words[i - 1], words[i]) > 0) return false;
        }
        return true;
    }
}

Both implementations run in O(N · L) time, where N is the number of words and L is the average word length, and use O(26) extra space for the rank mapping.