LeetCode 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 由小写英文字母组成

题目含义解析

赎金信：歹徒为了要赎金，并且防止字迹被认出，所以从杂志或报纸中，找对应的字母，然后拼成一封信，能不能拼成呢，就要求杂志中的字符比赎金中的多。

这个问题的核心在于判断一个给定的字符串（通常被视为“赎金信”或“目标字符串”）是否完全可以由另一个字符串（通常被视为“杂志”或“源字符串”）中的字符（且每个字符仅使用一次）组成。

实际就是ransomNote中每个字符出现的次数，要小于等于magazine中该字符出现的次数

比如ransomNote=abca ,a出现2次，b,1次，c，1次，magazine=aabcda,a：3次，b:1次，c:1次，d:1次，2<3,1=1,1=1,满足条件可以

思路

该问题可以用哈希表来解决

哈希表是根据关键码的值而直接进行访问的数据结构。例如数组，可以根据下标来获取对应元素

哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里

常见的三种哈希结构：

• 数组
• set （集合）
• map(映射)

该问题可以用一个哈希结构存储ransomNote每个字符出现次数，然后遍历magazine，当字符出现在哈希表中时，次数减一，如果次数已经是1，那么再减一次就是0了，直接移除掉该字符

如果次数大于1，那么次数减一

结果判断map是否为空，为空就说明都包含

代码

public boolean canConstruct(String ransomNote, String magazine) {int a=ransomNote.length();int b=magazine.length();Map<Character,Integer> map = new HashMap<>();//将ransomNote中的字符放入到数组中，键是字符，值是字符次数for(int i=0;i<a;i++){char c= ransomNote.charAt(i);map.put(c,map.getOrDefault(c,0)+1);}//for(int j=0;j<b;j++){char d= magazine.charAt(j);//map中包括当前字符if(map.containsKey(d)){//获取次数，判断次数等于一，再减掉一次就是0，直接移除int time = map.get(d);if(time==1){map.remove(d);}else{//次数>1，map中该字符次数减一map.put(d,time-1);}}}//最后map是空就说明是可以，否则就说明不可以return map.isEmpty();}

方法二：使用数组当做哈希结构

由于题目中说明都是因为小写字符，所以可以建立一个26个初始值为0的数组，

数组下标就是当前字符-'a',后的值，数组的值存出当前字符出现次数

例如’c‘-'a'=2,存储在下标为2的地方，

遍历magazine，存储当前字符出现次数，

遍历ransomNote，当前字符-’a‘ 位置处的值-1，如果减掉之后，已经小于0了，那么就直接返回false

public static boolean canConstruct1(String ransomNote, String magazine) {//存储当前字符出现次数int[] nums=new int[26];//看magazine中每个字符出现次数for(char a:magazine.toCharArray()){nums[a-'a']++;}//遍历ransomNotefor(char b :ransomNote.toCharArray()){//次数先-1nums[b-'a']--;//次数小于0，说明magazine中字符少，直接返回falseif(nums[b-'a']<0){return false;}}return true;}