408算法题leetcode--第五天

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){// 前面的字符都相等，如abc和abcdif(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;}
};