10.15 Verifying an Alien Dictionary

10.15.1 Problem Metadata

10.15.2 Description

Given the order of an alien alphabet and a lc-list of words, determine if the words appear in lexicographically increasing order according to that alien alphabet.

10.15.3 Examples

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

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

10.15.4 Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • order is a permutation of lowercase letters

10.15.5 Solution - Pairwise Comparison with Rank Map

10.15.5.1 Walkthrough

Precompute the order rank for each letter. Compare consecutive words character by character. The first differing letter determines ordering; if it violates the rank order, return false. Handle prefix cases by ensuring the longer word does not precede its prefix.

10.15.5.2 Analysis

  • Time Complexity: O(total letters)
  • Space Complexity: O(1)

10.15.5.3 Implementation Steps

  1. Build rank[26] where rank[c] gives order.
  2. For each adjacent pair (w1, w2):
    1. Scan up to min(len1, len2).
    2. If chars differ, compare via rank and stop.
    3. If all equal but len1 > len2, return false.
  3. Return true if no violations occur.

10.15.5.4 Code - Java

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 (!inOrder(words[i], words[i + 1], rank)) {
            return false;
        }
    }
    return true;
}

private boolean inOrder(String w1, String w2, int[] rank) {
    int len = Math.min(w1.length(), w2.length());
    for (int i = 0; i < len; i++) {
        char c1 = w1.charAt(i);
        char c2 = w2.charAt(i);
        if (c1 != c2) {
            return rank[c1 - 'a'] < rank[c2 - 'a'];
        }
    }
    return w1.length() <= w2.length();
}