力扣LCR034题：哈希表+双指针解决外星语词典

一、题目解读

力扣LCR034题要求判断一个字符串数组是否按照给定的外星语顺序排序。题目本质是自定义排序规则的验证，需处理相邻单词的字母比较及长度差异。

二、解题思路

采用“哈希表+双指针”策略：

1. 建立字母-顺序映射：通过哈希表将order中的每个字母映射到其索引位置（如a→0, b→1, c→2），便于快速比较字母大小。

2. 双指针逐对比较：遍历words中相邻单词，从左侧开始对比字符，若遇到不同字母，则通过映射值判断顺序是否合法；若所有相同字符后单词长度更长，则排序非法。

该思路将自定义排序转化为数值比较，避免了复杂的多条件判断，时间复杂度优化至O(n)，空间复杂度为O(m)（m为字母集大小）。

三、解题步骤

1. 构建映射表：遍历order，将字符c映射到索引i（orderMap[c] = i）。

2. 外层循环遍历单词对：对相邻单词word1和word2进行比较。

3. 内层双指针找差异：

    取两单词较短长度minLen，同步遍历字符。

    若字符不同，通过映射值判断是否word1[j] > word2[j]（即排序错误）。

    若遍历完minLen仍相同且word1更长，则排序非法（如"ab", "a"）。

4. 所有比较通过后返回true，否则false。

四、代码与注释

class Solution {
public:
    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;
    }
};

五、总结

本题通过哈希映射将外星字母转化为可比较的数值，结合双指针高效定位差异字符，避免了复杂的多条件判断。关键在于理解“自定义排序”可转化为数值比较，并利用映射表降低时间复杂度。对于涉及自定义规则的排序验证问题，建立映射表是常见优化手段，值得掌握。