0%

[Leetcode]383. Ransom Note(C++)

题目描述

题目链接: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 看所需字符是否满足数量即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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) 字母数量为常数