Easy

题目描述

在某种外星语中，令人惊讶的是，他们也使用英语小写字母，但可能顺序不同。字母表的顺序是小写字母的某种排列。

给定一系列用外星语书写的单词以及字母表的顺序，当且仅当给定的单词在这种外星语中按字典序排序时，返回 true。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 在 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 在 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：前三个字符 "app" 匹配，并且第二个字符串较短。根据字典序规则，"apple" > "app"，因为 'l' > ∅，其中 ∅ 定义为空白字符，小于任何其他字符。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • order.length == 26
  • words[i] 和 order 中的所有字符都是英语小写字母。

解题思路

这道题的关键是理解字典序比较的原理，然后根据给定的外星语字母顺序来进行比较。

核心思路：

  1. 建立映射关系：首先将外星语的字母顺序转换为数字映射，这样可以快速比较两个字符的大小关系
  2. 逐对比较相邻单词：只需要检查相邻的单词对是否满足字典序，如果所有相邻对都满足，整个序列就是有序的
  3. 字典序比较规则：对于两个字符串，从左到右逐字符比较，遇到第一个不同的字符时，字符较小的字符串在前；如果一个字符串是另一个的前缀，则较短的在前

比较函数实现：

  • 逐字符比较两个单词
  • 如果某个位置字符不同，根据外星语字母表判断大小关系
  • 如果所有字符都相同但长度不同，短的在前

推荐解法：使用哈希表存储字符到位置的映射，然后实现自定义比较函数。时间复杂度为 O(N×M)，其中 N 是单词数量，M 是平均单词长度。

代码实现

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> charOrder;
        for (int i = 0; i < 26; i++) {
            charOrder[order[i]] = i;
        }
        
        auto compare = [&](const string& word1, const string& word2) -> bool {
            int len1 = word1.length(), len2 = word2.length();
            int minLen = min(len1, len2);
            
            for (int i = 0; i < minLen; i++) {
                if (charOrder[word1[i]] < charOrder[word2[i]]) {
                    return true;
                } else if (charOrder[word1[i]] > charOrder[word2[i]]) {
                    return false;
                }
            }
            return len1 <= len2;
        };
        
        for (int i = 0; i < words.size() - 1; i++) {
            if (!compare(words[i], words[i + 1])) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        char_order = {char: i for i, char in enumerate(order)}
        
        def compare(word1, word2):
            min_len = min(len(word1), len(word2))
            for i in range(min_len):
                if char_order[word1[i]] < char_order[word2[i]]:
                    return True
                elif char_order[word1[i]] > char_order[word2[i]]:
                    return False
            return len(word1) <= len(word2)
        
        for i in range(len(words) - 1):
            if not compare(words[i], words[i + 1]):
                return False
        return True

public class Solution {
    public bool IsAlienSorted(string[] words, string order) {
        var charOrder = new Dictionary<char, int>();
        for (int i = 0; i < order.Length; i++) {
            charOrder[order[i]] = i;
        }
        
        bool Compare(string word1, string word2) {
            int minLen = Math.Min(word1.Length, word2.Length);
            for (int i = 0; i < minLen; i++) {
                if (charOrder[word1[i]] < charOrder[word2[i]]) {
                    return true;
                } else if (charOrder[word1[i]] > charOrder[word2[i]]) {
                    return false;
                }
            }
            return word1.Length <= word2.Length;
        }
        
        for (int i = 0; i < words.Length - 1; i++) {
            if (!Compare(words[i], words[i + 1])) {
                return false;
            }
        }
        return true;
    }
}

var isAlienSorted = function(words, order) {
    const charOrder = new Map();
    for (let i = 0; i < order.length; i++) {
        charOrder.set(order[i], i);
    }
    
    const compare = (word1, word2) => {
        const minLen = Math.min(word1.length, word2.length);
        for (let i = 0; i < minLen; i++) {
            if (charOrder.get(word1[i]) < charOrder.get(word2[i])) {
                return true;
            } else if (charOrder.get(word1[i]) > charOrder.get(word2[i])) {
                return false;
            }
        }
        return word1.length <= word2.length;
    };
    
    for (let i = 0; i < words.length - 1; i++) {
        if (!compare(words[i], words[i + 1])) {
            return false;
        }
    }
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N×M)N 是单词数量，M 是平均单词长度，需要比较所有相邻单词对
空间复杂度O(1)只需要固定大小的哈希表存储 26 个字母的映射关系