脚撕LeetCode(383)Easy
题目地址：https://leetcode-cn.com/problems/ransom-note/submissions/
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) https://leetcode-cn.com/problems/ransom-note/submissions/
示例 1： 输入：ransomNote = "a", magazine = "b" 输出：false 示例 2： 输入：ransomNote = "aa", magazine = "ab" 输出：false 示例 3： 输入：ransomNote = "aa", magazine = "aab" 输出：true 提示：你可以假设两个字符串均只含有小写字母。 https://leetcode-cn.com/problems/ransom-note/submissions/
这道题想着也是挺简单的，跟警匪片里面匪徒的勒索信类似，都需要从报纸上剪字，那么其实题目就已经理解了（毕竟你不可能剪出不存在的字符）
一、爆破法
首先想到的还是老套路，char数组，26长度，然后遍历杂志累加，遍历赎金信类减，如果减了之后小于0，则返回false
执行结果：
126 / 126 个通过测试用例
状态：通过
执行用时: 2 ms
内存消耗: 38.1 MB
public boolean canConstructMe(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) return false;
int[] dict = new int[26];
for (int i = 0; i < magazine.length(); i++) {
dict[magazine.charAt(i) - 'a']++;
}
int item = 0;
for (int i = 0; i < ransomNote.length(); i++) {
item = ransomNote.charAt(i) - 'a';
if (--dict[item] < 0)
return false;
}
return true;
}二、统计法
评论区大佬的想法基本类似，不同的是他的时间比我少1ms，大佬的做法是先统计需要的数量，然后遍历杂志的数量去减缓存的数组，如果数组的值=0则不做任何处理（即改不改没有意义了），并且做一个中间变量，统计赎金信的剩余字段长度
执行结果如下：
126 / 126 个通过测试用例
状态：通过
执行用时: 1 ms
内存消耗: 38.4 MB
public boolean canConstruct(String ransomNote, String magazine) {
// 统计 ransom 字符
int[] chars = new int[26];
int ransomLen = ransomNote.length();
for (int i = 0; i < ransomLen; i++) {
chars[ransomNote.charAt(i) - 97]++;
}
// 遍历 magazine
for (int i = 0, len = magazine.length(); i < len && ransomLen > 0; i++) {
if (chars[magazine.charAt(i) - 97] != 0) {
chars[magazine.charAt(i) - 97]--;
ransomLen--;
}
}
return ransomLen == 0;
}不得不说在自己以为自己已经做到自己觉得最好的时候，看了一下果然还是百密一疏。看来算法之路还很长，需要慢慢的加油啊。
腾讯云开发者
