力扣LCR034 验证外星语词典：字典序验证算法详解

一、问题理解

题目要求验证给定的单词列表是否按照自定义字母顺序（外星语字典序）排列。这与常规英文字典序验证类似，但字母顺序可能完全不同。

二、算法设计

1. 建立字母顺序映射：将外星语字母顺序转换为数值映射，便于比较

2. 逐对比较单词：检查相邻单词是否符合字典序

3. 处理边界情况：如空单词、相同单词等情况

三、C++实现代码

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

bool isAlienSorted(vector<string>& words, string order) {
    // 建立字母到顺序值的映射
    unordered_map<char, int> orderMap;
    for (int i = 0; i < order.size(); ++i) {
        orderMap[order[i]] = i;
    }
    
    // 比较每对相邻单词
    for (int i = 0; i < words.size() - 1; ++i) {
        string word1 = words[i];
        string word2 = words[i + 1];
        
        // 找到第一个不同的字母进行比较
        int minLen = min(word1.size(), word2.size());
        int j = 0;
        for (; j < minLen; ++j) {
            if (word1[j] != word2[j]) {
                if (orderMap[word1[j]] > orderMap[word2[j]]) {
                    return false;
                }
                break;
            }
        }
        
        // 如果前面字母都相同，但第一个单词更长，则无效
        if (j == minLen && word1.size() > word2.size()) {
            return false;
        }
    }
    
    return true;
}

四、代码解释

1. orderMap：存储每个字母在外星语中的顺序值

2. 相邻单词比较：逐个字母比较，直到找到不同字母

3. 特殊情况处理：处理前缀相同但长度不同的情况