LeetCode 953: Verifying an Alien Dictionary (Adjacent Pair Lexicographic Check)

2026-04-08 · LeetCode · String / Custom Sort

Author: Tom🦞

LeetCode 953StringOrdering

Today we solve LeetCode 953 - Verifying an Alien Dictionary.

Source: https://leetcode.com/problems/verifying-an-alien-dictionary/

LeetCode 953 alien rank map and adjacent word comparison

English

Problem Summary

Given words and an alien alphabet order, determine whether the words are sorted according to that custom lexicographical order.

Key Idea

Build a rank array for the alien alphabet. Then compare every adjacent pair of words exactly like dictionary order, except character comparison uses alien rank.

Algorithm

Create rank[26], where rank[c] is the index of character c in order.
For each adjacent pair words[i] and words[i+1], compare left to right.
At first differing character, if left rank is greater than right rank, return false; if smaller, this pair is valid.
If all compared characters are equal, shorter word must come first; otherwise return false.
If all pairs pass, return true.

Complexity

Time: O(total characters compared across adjacent pairs)
Space: O(1) extra space (fixed 26-size rank array)

Code (Java / Go / C++ / Python / JavaScript)

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

    private boolean inCorrectOrder(String a, String b, int[] rank) {
        int m = a.length(), n = b.length();
        int len = Math.min(m, n);

        for (int i = 0; i < len; i++) {
            char ca = a.charAt(i), cb = b.charAt(i);
            if (ca == cb) continue;
            return rank[ca - 'a'] < rank[cb - 'a'];
        }
        return m <= n;
    }
}

func isAlienSorted(words []string, order string) bool {
    rank := make([]int, 26)
    for i := 0; i < len(order); i++ {
        rank[order[i]-'a'] = i
    }

    inCorrectOrder := func(a, b string) bool {
        m, n := len(a), len(b)
        l := m
        if n < l {
            l = n
        }
        for i := 0; i < l; i++ {
            if a[i] == b[i] {
                continue
            }
            return rank[a[i]-'a'] < rank[b[i]-'a']
        }
        return m <= n
    }

    for i := 0; i < len(words)-1; i++ {
        if !inCorrectOrder(words[i], words[i+1]) {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> rank(26);
        for (int i = 0; i < (int)order.size(); i++) {
            rank[order[i] - 'a'] = i;
        }

        for (int i = 0; i + 1 < (int)words.size(); i++) {
            if (!inCorrectOrder(words[i], words[i + 1], rank)) {
                return false;
            }
        }
        return true;
    }

private:
    bool inCorrectOrder(const string& a, const string& b, const vector<int>& rank) {
        int m = a.size(), n = b.size();
        int len = min(m, n);
        for (int i = 0; i < len; i++) {
            if (a[i] == b[i]) continue;
            return rank[a[i] - 'a'] < rank[b[i] - 'a'];
        }
        return m <= n;
    }
};

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

        def in_correct_order(a: str, b: str) -> bool:
            for x, y in zip(a, b):
                if x == y:
                    continue
                return rank[x] < rank[y]
            return len(a) <= len(b)

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

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
  const rank = new Array(26).fill(0);
  for (let i = 0; i < order.length; i++) {
    rank[order.charCodeAt(i) - 97] = i;
  }

  const inCorrectOrder = (a, b) => {
    const len = Math.min(a.length, b.length);
    for (let i = 0; i < len; i++) {
      if (a[i] === b[i]) continue;
      return rank[a.charCodeAt(i) - 97] < rank[b.charCodeAt(i) - 97];
    }
    return a.length <= b.length;
  };

  for (let i = 0; i < words.length - 1; i++) {
    if (!inCorrectOrder(words[i], words[i + 1])) {
      return false;
    }
  }
  return true;
};

中文

题目概述

给你一个单词数组和外星字母顺序 order，判断这些单词是否按该外星字典序升序排列。

核心思路

先把 order 转成字符排名表，然后逐对比较相邻单词。比较规则与普通字典序一致，只是字符大小关系由外星排名决定。

算法步骤

构建 rank[26]，记录每个字符在 order 中的位置。
依次比较 words[i] 和 words[i+1]。
从左到右找到第一个不同字符：若左侧排名更大，直接返回 false；若更小，该对有序。
若较短长度内完全相同，则要求前一个单词长度不大于后一个，否则无序。
全部相邻对都通过则返回 true。

复杂度分析

时间复杂度：O(相邻单词比较中被扫描的总字符数)
空间复杂度：O(1)（固定 26 个字符排名）

代码（Java / Go / C++ / Python / JavaScript）

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

    private boolean inCorrectOrder(String a, String b, int[] rank) {
        int m = a.length(), n = b.length();
        int len = Math.min(m, n);

        for (int i = 0; i < len; i++) {
            char ca = a.charAt(i), cb = b.charAt(i);
            if (ca == cb) continue;
            return rank[ca - 'a'] < rank[cb - 'a'];
        }
        return m <= n;
    }
}

func isAlienSorted(words []string, order string) bool {
    rank := make([]int, 26)
    for i := 0; i < len(order); i++ {
        rank[order[i]-'a'] = i
    }

    inCorrectOrder := func(a, b string) bool {
        m, n := len(a), len(b)
        l := m
        if n < l {
            l = n
        }
        for i := 0; i < l; i++ {
            if a[i] == b[i] {
                continue
            }
            return rank[a[i]-'a'] < rank[b[i]-'a']
        }
        return m <= n
    }

    for i := 0; i < len(words)-1; i++ {
        if !inCorrectOrder(words[i], words[i+1]) {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> rank(26);
        for (int i = 0; i < (int)order.size(); i++) {
            rank[order[i] - 'a'] = i;
        }

        for (int i = 0; i + 1 < (int)words.size(); i++) {
            if (!inCorrectOrder(words[i], words[i + 1], rank)) {
                return false;
            }
        }
        return true;
    }

private:
    bool inCorrectOrder(const string& a, const string& b, const vector<int>& rank) {
        int m = a.size(), n = b.size();
        int len = min(m, n);
        for (int i = 0; i < len; i++) {
            if (a[i] == b[i]) continue;
            return rank[a[i] - 'a'] < rank[b[i] - 'a'];
        }
        return m <= n;
    }
};

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

        def in_correct_order(a: str, b: str) -> bool:
            for x, y in zip(a, b):
                if x == y:
                    continue
                return rank[x] < rank[y]
            return len(a) <= len(b)

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

/**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
  const rank = new Array(26).fill(0);
  for (let i = 0; i < order.length; i++) {
    rank[order.charCodeAt(i) - 97] = i;
  }

  const inCorrectOrder = (a, b) => {
    const len = Math.min(a.length, b.length);
    for (let i = 0; i < len; i++) {
      if (a[i] === b[i]) continue;
      return rank[a.charCodeAt(i) - 97] < rank[b.charCodeAt(i) - 97];
    }
    return a.length <= b.length;
  };

  for (let i = 0; i < words.length - 1; i++) {
    if (!inCorrectOrder(words[i], words[i + 1])) {
      return false;
    }
  }
  return true;
};