953.验证外星语词典

链接：953.验证外星语词典
难度：Easy
标签：数组、哈希表、字符串
简介：给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

题解 1 - cpp

• 编辑时间：2021-12-23
• 执行用时：4ms
• 内存消耗：9.1MB
• 编程语言：cpp
• 解法介绍：转换成地球文进行比较。

class Solution {
   public:
    bool isAlienSorted(vector<string> &words, string order) {
        int nums[30] = {0};
        for (int i = 0; i < order.size(); i++) nums[order[i] - 'a'] = i;
        for (auto &str : words) {
            for (auto &ch : str) {
                ch = nums[ch - 'a'] + 'a';
            }
        }
        for (int i = 1; i < words.size(); i++) {
            if (words[i] < words[i - 1]) return 0;
        }
        return 1;
    }
};

题解 2 - cpp

• 编辑时间：2022-05-17
• 执行用时：4ms
• 内存消耗：9.1MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    bool isAlienSorted(vector<string> &words, string order) {
        char map[26] = {0};
        for (int i = 0; i < order.size(); i++) map[order[i] - 'a'] = i;
        string prev = words[0];
        for (int i = 1; i < words.size(); i++) {
            if (!check(prev, words[i], map)) return false;
            prev = words[i];
        }
        return true;
    }
    bool check(string &s1, string &s2, char *map) {
        int i1 = 0, n1 = s1.size(), i2 = 0, n2 = s2.size();
        while (i1 < n1 && i2 < n2) {
            if (map[s1[i1] - 'a'] > map[s2[i2] - 'a']) return false;
            if (map[s1[i1] - 'a'] < map[s2[i2] - 'a']) return true;
            i1++;
            i2++;
        }
        return i1 == n1;
    }
};