Question

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

Analyze

这道题目使用两个string(string ransomNote, string magazine)作为输入，如果第二个string里面包含第一个string，那么就返回true, 如果不是那么就返回来false.

• 使用hashmap存入所有的string magazine里面的每一个char
• 然后再扫描string ransomNote里面的每一个char，在存在的hashmap里面去查找是否有这一个字符，如果有，那么就把这个字符自减一，如果没有，那么放回false

Solution

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