【LeetCode】 383. Ransom Note

Description

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.

給予你任意的贖身訊息字串和另一個字串包含所有從雜誌上截下來的字母，寫一個程式，如果贖身訊息可以從雜誌構成，回傳 true ；否則回傳 false。

每個從雜誌截下來的字母都只能使用一次。

提示：
你可以假設兩個字串都只包含小寫英文字母。

Example:

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

Solution

• 先建立一個hash，並跑一次雜誌字串，將每個字母出現的次數記錄下來。
• 再跑一次訊息字串，去hash把出現的字母次數減一，如果一直都大於零就為true；否則為false。

Code

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

tags: LeetCode C++