leetcode-383.赎金信

题源

383.赎金信

题目描述

给你两个字符串：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 由小写英文字母组成

思考

思考一 – 哈希表 – 数组

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

那么magazine的长度必然>=ransomNote

开辟一个vector容器，先给magazine包含的字母计数+，再给ransomNote中的字母计数-，只要vector最

终没有负数元素，则返回true

剪枝

如果magazine的长度<ransomNote的长度，那么必然不能构成ransomNote,这就可以进行剪枝

实现思考一代码

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {//如果magazine 中的每个字符只能在 ransomNote 中使用一次，那么magazine的长度必然>=ransomNote//哈希表 -- 数组//开辟一个vector容器，先给magazine包含的字母计数+，再给ransomNote中的字母计数-，只要vector最终没有负数元素，则返回trueint mlength = magazine.length();int rlength = ransomNote.length();if(mlength < rlength)   return false;vector<int> count(26,0);//给magazine包含的字母计数+for (char c : magazine){count[c-'a']++;}//再给ransomNote中的字母计数-for (char c : ransomNote){count[c-'a']--;}//判断有没有负数元素for (int i : count){//有负数元素if(i < 0)   return false;}//没有负数元素return true;}
};

在这里插入图片描述
最后剪枝的用时和不剪的用时一样

说明在这个题的样例中这种magazine的长度<ransomNote的长度的情况很少。

时间复杂度分析

三个循环的时间复杂度都是O(n)
综合来看，该算法的时间复杂度仍然是O(n)

思考一代码二

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int recode[26] = {0};//这里可以不剪// if(ransomNote.size() > magazine.size()){//     return false;// }for(int i = 0; i < magazine.length(); i++){recode[magazine[i] - 'a']++;}for(int i = 0; i < ransomNote.length(); i++){recode[ransomNote[i] - 'a']--;if(recode[ransomNote[i] - 'a'] < 0){return false;}}return true;}
};

反而更快
在这里插入图片描述

时间复杂度分析

两个循环的时间复杂度都是O(n)

综合来看，该算法的时间复杂度仍然是O(n)

思考二 – 暴力

用两层循环，外层循环表示magazine，内层循环表示ransomNote

在ransomNote中找到与magazine相同的字母，如有相同，将该

ransomNote的元素删除，然后遍历下一个magazine

最后判断ransomNote是否为空

实现思考二代码

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {for (int i = 0; i < magazine.size();i++){for (int j = 0; j < ransomNote.size();j++){if (magazine[i] == ransomNote[j]){ransomNote.erase(ransomNote.begin()+j);//不能重复使用同一个magazine[i]break;}}}if (ransomNote.empty()) return true;return false;}
};