leetcode 383. Ransom Note HashMap 统计字符 + HashMap

淡淡的烟草味﹌ 2022-06-07 02:51 135阅读 0赞

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:  
You may assume that both strings contain only lowercase letters.

canConstruct(“a”, “b”) -> false  
canConstruct(“aa”, “ab”) -> false  
canConstruct(“aa”, “aab”) -> true

直接使用HashMap遍历即可。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    class Solution 
    {
        public boolean canConstruct(String ransomNote, String magazine) 
        {
            if(ransomNote==null || magazine==null || ransomNote.length()>magazine.length())
                return false;
    
            Map<Character, Integer> map=new HashMap<>();
            for(int i=0;i<magazine.length();i++)
                map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0)+1);     
            for(int i=0;i<ransomNote.length();i++)
            {
                if(map.containsKey(ransomNote.charAt(i))==false)
                    return false;
                else 
                {
                    int size=map.get(ransomNote.charAt(i));
                    if(size==1)
                        map.remove(ransomNote.charAt(i));
                    else 
                        map.put(ransomNote.charAt(i), size-1);
                }
            }
            return true;
        }
    }

下面是C++的做法，自己利用一个数组做统计即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool canConstruct(string ransomNote, string magazine) 
        {
            vector<int> count(26, 0);
            for (char c : magazine)
                count[c - 'a']++;
            for(char c : ransomNote)
            {
                count[c - 'a']--;
                if (count[c - 'a'] < 0)
                    return false;
            }
            return true;
        }
    };