Verifying an Alien Dictionary

easy array hash map string

Problem

Given a list of words and the order of letters in an alien alphabet, return whether the words are sorted lexicographically.

Inputwords=["hello","leetcode"], order="hlabcdefgijkmnopqrstuvwxyz"

Outputtrue

Map each alien letter to its rank, then check each adjacent pair.

words (space-separated)

order (26 unique letters)

def isAlienSorted(words, order):
    rank = {c: i for i, c in enumerate(order)}
    for i in range(len(words) - 1):
        a, b = words[i], words[i + 1]
        for j in range(min(len(a), len(b))):
            if a[j] != b[j]:
                if rank[a[j]] > rank[b[j]]: return False
                break
        else:
            if len(a) > len(b): return False
    return True

function isAlienSorted(words, order) {
  const rank = new Map();
  for (let i = 0; i < order.length; i++) rank.set(order[i], i);
  for (let i = 0; i < words.length - 1; i++) {
    const a = words[i], b = words[i + 1];
    let differ = false;
    for (let j = 0; j < Math.min(a.length, b.length); j++) {
      if (a[j] !== b[j]) {
        if (rank.get(a[j]) > rank.get(b[j])) return false;
        differ = true; break;
      }
    }
    if (!differ && a.length > b.length) return false;
  }
  return true;
}

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] rank = new int[26];
        for (int i = 0; i < 26; i++) rank[order.charAt(i) - 'a'] = i;
        for (int i = 0; i < words.length - 1; i++) {
            String a = words[i], b = words[i + 1];
            int len = Math.min(a.length(), b.length());
            boolean differ = false;
            for (int j = 0; j < len; j++) {
                if (a.charAt(j) != b.charAt(j)) {
                    if (rank[a.charAt(j) - 'a'] > rank[b.charAt(j) - 'a']) return false;
                    differ = true; break;
                }
            }
            if (!differ && a.length() > b.length()) return false;
        }
        return true;
    }
}

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

Explanation

To check whether the words are in alien-sorted order, we just need to confirm that every neighbor pair is in order. If word 0 comes before word 1, and word 1 before word 2, and so on, the whole list is sorted.

The alien alphabet is custom, so we first build a rank map with rank = {c: i for i, c in enumerate(order)}. This turns each letter into a number telling us its position in the alien order, so we can compare letters as easily as comparing integers.

For each adjacent pair a and b, we scan their letters together. At the first position where they differ, we compare ranks: if rank[a[j]] > rank[b[j]], then a should come after b, which breaks sorted order, so we return False. Once we find a differing letter, this pair is decided and we stop.

If we never find a difference (one word is a prefix of the other), the shorter word must come first. So if a is longer than b (the else on the loop runs when no break happened), that is wrong and we return False.

Example: with order "hlabcdefgijkmnopqrstuvwxyz", comparing "hello" and "leetcode", the first letters differ: h has rank 0 and l has rank 1, so h comes first and the pair is fine. All pairs pass, so the answer is true.

Time: O(total chars) Space: O(1)