验证外星语词典

发表于 分类于 ， 阅读次数： Waline： 本文字数： 2k 阅读时长 ≈ 2 分钟

953. 验证外星语词典

某种外星语也使用英文小写字母，但可能顺序 order不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

输出：true

解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

思路

方法一

我们把外星语转化为正常的英语序，最后判断是否按照字典序排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char,int> mp;
        //哈希表确定位置
        for(int i = 0; i < order.size(); i++){
            mp[order[i]] = i;
        }
        vector<string> tmp;
        // 把外星语转化为正常英语序，最后判断是否有序
        for(string& word : words){
            string tmpWord;
            for(char c : word){
                tmpWord += 'a' + mp[c];
            }
            tmp.emplace_back(tmpWord);
        }
        return is_sorted(tmp.begin(), tmp.end());
    }
};

M为 words数组对长度，N为平均的单词长度 时间复杂度为O(M*N) 空间复杂度为O(N)

方法二：

我们只需要相邻的两个字符串是否按照给定的序列排列即可，这样就可以压缩空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution1 {
public:
    bool isAlienSorted(vector<string>& words, string order) {
       unordered_map<char, int> mp;
       for(int i = 0; i < order.size(); i++){
           mp[order[i]] = i;
       }
       for(int i = 0; i < words.size() - 1; i++){
           string pre = words[i];
           string cur = words[i + 1];
           bool res = false;
           for(int j = 0; j < min(pre.size(), cur.size()); j++){
               if(mp[pre[j]] < mp[cur[j]]){
                   res = true;
                   break;
               }else if(mp[pre[j]] > mp[cur[j]]){
                   return false;
               }
           }
           // 如果前面都相等，则判断长度
           if(!res && pre.size() > cur.size()){
               return false;
           }
       }
       return true;
    }
};