力扣-383题赎金信（C++）- string + 数组哈希

妖狐艹你老母 2022-08-30 05:25 142阅读 0赞

题目链接：[https://leetcode-cn.com/problems/ransom-note/][https_leetcode-cn.com_problems_ransom-note]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
解法一：数组哈希

class Solution {
        
    public:
        bool canConstruct(string ransomNote, string magazine) {
        
            //在本题的情况下，使用map的空间消耗要比数组大一些的，
            //因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！
            //数据量大的话就能体现出来差别了。所以数组更加简单直接有效！
    
            int array[26]={
        0};
            for(auto ch:magazine)
            array[ch-'a']++;
    
            for(auto ch:ransomNote)
            if(array[ch-'a']!=0) array[ch-'a']--;
            else return false;
    
            return true;
    
        }
    };

解法二：umap

class Solution {
        
    public:
        bool canConstruct(string ransomNote, string magazine) {
        
            unordered_map<char,int> hash;
            
            for(int i=0;i<magazine.size();i++){
        
                hash[magazine[i]]++;
            }
    
            for(int i=0;i<ransomNote.size();i++){
        
                if(hash[ransomNote[i]]>0){
        
                    hash[ransomNote[i]]--;
                }
                else return false;
            }
    
            return true;
        }
    };

[https_leetcode-cn.com_problems_ransom-note]: https://leetcode-cn.com/problems/ransom-note/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/4582b618f95d47d2807dbdba03244425.png