面试面试经典 150 题 - 哈希

383. 赎金信 - 一个哈希表搞定

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int hash[26] = {0};for (auto& ch : magazine) {hash[ch - 'a']++;}for (auto& ch : ransomNote) {if (--hash[ch - 'a'] < 0) {return false;}}return true;}
};

⭐️⭐️⭐️205. 同构字符串 - 双向映射 - 两个哈希表

错误写法

// 错误写法
class Solution {
public:bool isIsomorphic(string s, string t) {if (s.size() != t.size()) return false;int hash_s[26] = {0}, hash_t[26] = {0};for (int i = 0; i < s.size(); ++i) {if (++hash_s[s[i] - 'a'] != ++hash_t[t[i] - 'a']) {return false;}}return true;}
};

双向映射 - 两个大小为128 的array

class Solution {
public:// 注意：s 和 t 由任意有效的 ASCII 字符组成// --> array 大小为128，而不是 26bool isIsomorphic(string s, string t) {if (s.size() != t.size()) return false;array<char, 128> s2t = {0};array<char, 128> t2s = {0}; for (int i = 0; i < s.size(); ++i) {char s_char = s[i];char t_char = t[i];if (s2t[s_char] == 0 && t2s[t_char] == 0) {s2t[s_char] = t_char;t2s[t_char] = s_char;} else if (s2t[s_char] != t_char || t2s[t_char] != s_char) {return false;}}return true;}
};