953. 验证外星语词典
- 953. 验证外星语词典
- 思路：先用哈希表建立优先级，再进行排序
- 时间：O(mn)，m、n分别是words和string的长度；空间：O(1)，小写字母26个
class Solution {
public:bool isAlienSorted(vector<string>& words, string order) {vector<int>cmp(26, 0);int size = order.size();for(int i = 0; i < size; i++){cmp[order[i] - 'a'] = i;}size = words.size();for(int i = 1; i < size; i++){bool flag = false;for(int j = 0; j < words[i - 1].size() && j < words[i].size(); j++){if(cmp[words[i - 1][j] - 'a'] < cmp[words[i][j] - 'a']){flag = true;break;} else if(cmp[words[i - 1][j] - 'a'] > cmp[words[i][j] - 'a']) {return false;}}if(!flag){if(words[i - 1].size() > words[i].size()){return false;}}}return true;}
};
242. 有效的字母异位词
- 242. 有效的字母异位词
- 思路：建立两个哈希表，然后对比是否相同
- 时间：O(n)，即遍历两次字符串，然后遍历一次哈希表；空间：O(1)
class Solution {
public:bool isAnagram(string s, string t) {int hash_s[26] = {0}, hash_t[26] = {0};for(auto c : s){hash_s[c - 'a']++; }for(auto c : t){hash_t[c - 'a']++; }for(int i = 0; i < 26; i++){if(hash_s[i] != hash_t[i]){return false;}}return true;}
};
389. 找不同
- 389. 找不同
- 思路：可以和上一题的思路一样；也可以先对S和T字符串的ascii值求和，然后相减就是答案；同时也可以用位运算，如a^a =0, ab ^ ab = 0, 而ab ^ abc = c
- 时间：O(n)；空间：O(1)
class Solution {
public:char findTheDifference(string s, string t) {int ss = 0, tt = 0;for(auto c : s){ss += c;}for(auto c : t){tt += c;}return tt - ss;}
};
