面试算法之哈希专题

赎金信

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 小写字母
        int r_cnt[26];
        int m_cnt[26];
        for(int i = 0; i< magazine.size(); i++) {
            m_cnt[magazine[i]-'a']++; // 统计
        }
        // 对比

        for(int i = 0; i< ransomNote.size(); i++) {
            if(m_cnt[ransomNote[i]-'a']) {
                m_cnt[ransomNote[i]-'a']--;
            } else {
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 小写字母
        int r_cnt[26];
        int m_cnt[26];
        for(int i = 0; i< magazine.size(); i++) {
            m_cnt[magazine[i]-'a']++; // 统计
        }
        // 对比

        for(int i = 0; i< ransomNote.size(); i++) {
            if(m_cnt[ransomNote[i]-'a']) {
                m_cnt[ransomNote[i]-'a']--;
            } else {
                return false;
            }
        }
        return true;
    }
};

同构字符串

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char,char> s_map;
        unordered_map<char,char> t_map;

        int s_size = s.size();
        int t_size = t.size();
        if(s_size != t_size) {
            return false;
        } 
        for(int i = 0; i< s_size; i++) {
            char x = s[i];
            char y = t[i];
            if((s_map.count(x) && s_map[x] != y) || (t_map.count(y) && t_map[y] != x)) {
                return false;
            }

            s_map[x] = y;
            t_map[y] = x;
        }
    return true;    
    }
};

收获

了解了一下 有关于 unordered_map 中 count 函数的使用
s_map.count(x) 就是 键为 x 的个数

逐步解析

方法二
思路

通过 match 建立关系
通过 count 记录 t[i] 是否已经有映射

这部分是表示, 不存在 s[i] 的映射, 但是发现 t[i] 已经做好映射了 ( count[t[i]] > 0 ) 直接返回 false

  			if (match[s[i]] == '\0') { // 如果当前字符没有映射关系
                if (count[t[i]] == 0) { // 如果当前字符在t中没有出现过
                    match[s[i]] = t[i]; // 建立映射关系
                    count[t[i]] = 1; // 将该字符在t中的出现次数加1
                }
                else
                    return false; // 如果当前字符在t中已经出现过，则返回false
            }

图解

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> match; // 用于存储字符之间的映射关系
        unordered_map<char, int> count; // 用于记录字符在t中出现的次数
        
        for (int i = 0; i < s.size(); i++) {
            if (match[s[i]] == '\0') { // 如果当前字符没有映射关系
                if (count[t[i]] == 0) { // 如果当前字符在t中没有出现过
                    match[s[i]] = t[i]; // 建立映射关系
                    count[t[i]] = 1; // 将该字符在t中的出现次数加1
                }
                else
                    return false; // 如果当前字符在t中已经出现过，则返回false
            }
            else { // 如果当前字符已经有映射关系
                if (match[s[i]] != t[i]) { // 如果映射关系不正确
                    return false; // 返回false
                }
            }
        }
        return true; // 所有字符都满足同构条件，返回true
    }
};

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<string,char> s_patterMap;
        unordered_map<char, string> pattern_sMap;

        // 遍历
       int p_len = pattern.size();
       int left = 0;
       int right = 0;
       for(int i = 0; i< p_len ; i++) {
            if(left >= s.size()) {
                return false;
            }
            // 遍历
            while(right < s.size() && s[right] != ' ') right++;
            // 右边界 right 
            string str = s.substr(left, right-left);
            
            if(s_patterMap.count(str) && s_patterMap[str] != pattern[i]) {
                return false;
            }
            if(pattern_sMap.count(pattern[i]) && pattern_sMap[pattern[i]] != str) {
                return false;
            }

            s_patterMap[str] = pattern[i];
            pattern_sMap[pattern[i]] = str;
            left = right + 1;
            right = left;
        }
        if(right < s.size()) {
            return false;
        } else {
            return true;
        }
    }
};