📃 题目描述

题目链接：

• 剑指 Offer II 034. 外星语言是否排序 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 953. 验证外星语词典 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

理解题意比较重要

就是根据 order 给出的顺序，来判断 words 中的单词顺序是不是对的

举个例子，word 和 world 这两个单词，order = "wor lab dcefghijkmnpqstuvxyz"

前三个一模一样，没得说。

第四个字符，在 order 中的顺序是 l < d，所以 world 应该排在 word 的前面

如果两个单词前缀一样，那么谁短谁排前面，比如 app 应该排在 apple 的前面

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        // 构造存储字母表顺序的 map
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < order.length(); i ++) {
            map.put(order.charAt(i), i);
        }

        for (int i = 0; i < words.length - 1; i ++) {
            String word1 = words[i];
            String word2 = words[i + 1];

            if (!isSorted(word1, word2, map)) {
                return false;
            }
        }

        return true;
    }

    private boolean isSorted(String word1, String word2, Map<Character, Integer> map) {
        for (int i = 0; i < word1.length() && i < word2.length(); i ++) {
            if (word1.charAt(i) == word2.charAt(i)) {
                continue;
            }
          
            int index1 = map.get(word1.charAt(i));
            int index2 = map.get(word2.charAt(i));
            if (index1 < index2) {
                return true;
            }
            else if (index1 > index2) {
                return false;
            }
        }

        // 能够走到这里说明前面的字符都是完全相同的(那么短的单词在排序的时候应该排在前面)
        return word1.length() <= word2.length();
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N^2)