题目描述
题目链接:383. Ransom Note
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.
例子
例子 1
Input: ransomNote = “a”, magazine = “b” Output: false
例子 2
Input: ransomNote = “aa”, magazine = “ab” Output: false
例子 3
Input: ransomNote = “aa”, magazine = “aab” Output: true
Constraints
- You may assume that both strings contain only lowercase letters.
解题思路
这道题要求判断 ransomNote
中的字符串能否用 magazine
中的字符组成,思路比较清晰。可以用一个哈希表统计 magazine
中的出现的字符以及对应次数;再遍历一次 ransomNote
看所需字符是否满足数量即可,代码如下:
#include <string>
#include <vector>
class Solution {
public:
bool canConstruct(std::string ransomNote, std::string magazine) {
std::vector<int> count(26, 0);
for (char letter: magazine) {
count[letter - 'a']++;
}
for (char letter: ransomNote) {
count[letter - 'a']--;
if (count[letter - 'a'] < 0) return false;
}
return true;
}
};
- 时间复杂度: O(n + m)
- 空间复杂度: O(1) 字母数量为常数