383. 赎金信【 力扣(LeetCode) 】

一、题目描述

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

二、测试用例

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

三、解题思路

1. 基本思路：
     统计每个字符的频率，然后判断字符够不够用
2. 具体思路：
   • 统计字符频率：遍历 magazine ，统计每个字符的频率。【都是小写字母组成，所以可以直接开 26 个 int 空间】
   • 计算字符使用率：遍历 ransomNote ，判断字符够不够使用，不够就返回 false ；够就返回 true ；

四、参考代码

时间复杂度：$\mathrm{O}(n+m)$
空间复杂度：$\mathrm{O}(1)$ 【vector 固定 26 个 int 空间】

class Solution {
public:vector<int> init(string magazine, int n) {vector<int> ans(26,0);for (int i = 0; i < n; i++) {ans[magazine[i]-'a']++;}return ans;}bool canConstruct(string ransomNote, string magazine) {int n = ransomNote.length(), m = magazine.length();vector<int> fluence = init(magazine, m);for (int i = 0; i < n; i++) {if(--fluence[ransomNote[i]-'a']==-1){return false;}}return true;}
};