Example 2
赎金信
题目概述：给你两个字符串：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
解题思路：题目要求使用字符串 magazine 中的字符来构建新的字符串 ransomNote，且ransomNote 中的每个字符只能使用一次，只需要满足字符串 magazine 中的每个英文字母 (’a’-’z’) 的统计次数都大于等于 ransomNote 中相同字母的统计次数即可。
解题步骤：
1. 首先比较两个字符串的长度，若字符串 magazine 的长度小于字符串 ransomNote 的长度，则可以肯定 magazine 无法构成 ransomNote，直接返回false。
2. 定义长度为26的数组cnt代表依次26个字母出现的次数。
3. 统计 magazine 中每个英文字母 c 的出现次数 cnt[c]，因各个字母在ASCⅡ码中都有对应的序号且是依次递增的，因此将每个英文字母减去最小的英文字母’a’，其值为该英文字母在字母表中的序号，并将其自加一，代表多出现了一次。
4. 再用同样的方法遍历统计 ransomNote 中每个英文字母出现的次数。某英文字母c出现一次，则将统计magazine 中该英文字母 c 的出现次数 cnt[c]自减一，以此来比较该英文字母在两个字符串中出现次数的多少。
若发现 ransomNote 中存在某个英文字母 c 的统计次数大于 magazine 中该字母统计次数 cnt[c]，则说明该字母在magazine 中出现的次数都小于在ransomNote中出现的次数，无法构建，返回false。
若否则遍历结束后，数组cnt中每个元素均没有出现小于0的情况，说明magazine 中每个字母出现的次数都大于等于ransomNote中对应字母的出现次数，可以构建，返回true。
示例代码如下：
publicclassRansomLetter { /*** 给你两个字符串：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* 来源：力扣（LeetCode）* 链接：https://leetcode.cn/problems/ransom-note*/publicstaticvoidmain(String[] args) { System.out.println(canConstruct("aa", "aab")); } /*** 个人* @param ransomNote* @param magazine* @return*//* public static boolean canConstruct(String ransomNote, String magazine) {List<Character> ransomNoteList = new ArrayList<>();for (int i = 0; i < ransomNote.length(); i++) {ransomNoteList.add(ransomNote.charAt(i));}List<Character> magazineList = new ArrayList<>();for (int i = 0; i < magazine.length(); i++) {magazineList.add(magazine.charAt(i));}OUT:for (Character s1 : ransomNoteList) {for (Character s2 : magazineList) {if (s1.equals(s2)) {magazineList.remove(s2);continue OUT;}}return false;}return true;}*//*** 官方* @param ransomNote* @param magazine* @return*/publicstaticbooleancanConstruct(StringransomNote, Stringmagazine) { if (ransomNote.length() >magazine.length()) { returnfalse; } int[] cnt=newint[26]; for (charc : magazine.toCharArray()) { cnt[c-'a']++; } for (charc : ransomNote.toCharArray()) { cnt[c-'a']--; if(cnt[c-'a'] <0) { returnfalse; } } returntrue; } }
