题目
验证外星语词典
思路
暴力解法：将 words中的单词按照 order 的字典序进行排序后与原数组进行对比，若相同则返回 true，若存在不同则返回 false
题解
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
28
29
| class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
unordered_map<char, int> hsp;
int num = 0;
for(int i = 0; i < order.size(); i++){
hsp[order[i]] = num ++;
}
vector<string> arr;
for(int i = 0; i < words.size(); i++){
arr.emplace_back(words[i]);
}
sort(arr.begin(), arr.end(), [&](string &a, string &b){
int len_a = a.size();
int len_b = b.size();
int len = min(len_a, len_b);
for(int i = 0; i < len; i++){
if(a[i] == b[i]) continue;
return hsp[a[i]] < hsp[b[i]];
}
return len_a < len_b;
});
for(int i = 0; i < arr.size(); i++){
if(arr[i] != words[i])
return false;
}
return true;
}
};
|
- 时间复杂度：O(n \ logn)，其中 n* 是数组中元素的个数
- 空间复杂度：O(n)，需要另外一个数组保存排序后的words
执行用时：8 ms, 在所有 C++ 提交中击败了28.37%的用户
内存消耗：10.1 MB, 在所有 C++ 提交中击败了5.05%的用户
通过测试用例：120 / 120