Leetcode Study Day 19

Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true
 

Constraints:

1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.

My solution

My solution is creating an unordered_map to store each character in the string magazine. We count how many times each character appear.

Then we loop the string ransomNote and check if the character is in the unordered_map. If it is, we decrease the count by 1. If it is not, we return false.
If the count for this character is already equal to 0, which means this character has already appeared once, than we return false.

One knowledge need to methion is that in C++ unordered_map, if the key is not in the map, the find() function will return the end() iterator.

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