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 <= 105ransomNote和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;}