算法——赎金信（leetcode383）

题目：

给你两个字符串：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需要使magazine的总字符数量及类别包含ransomNote

也就是图片所示

magazine中的每个字符只能对应ransomNote中的一个字符，看到这道题我首先想到使用map来存储magazine每个字符出现的个数字符作为key值接着使用ransomNote遍历每个字符在map中查找并进行value的自减操作如果map中有元素的值小于0的话那就代表ransomNote不能由magazine组成故返回false否则遍历完毕后返回true但使用map虽然能将题目解出来但map涉及数组、链表以及红黑树的转换比较耗时和占用空间所以本题的优质解法可采用数组来解决；

map解法:

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap();
        for (int i = 0; i < magazine.length(); i++) {
            map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            map.put(ransomNote.charAt(i), map.getOrDefault(ransomNote.charAt(i), 0) - 1);
            if (map.get(ransomNote.charAt(i)) == null || map.get(ransomNote.charAt(i)) < 0)
                return false;
        }
        return true;
    }
}

数组解法:

附加:先判断ransomNote 长度是否大于magazine 如果大于则直接返回false

1、创建一个长度为26的数组（因为英文字母26个）

2、遍历magazine 字符串将其字符减去‘a’的ASCLL码获得数值0~26的索引下标对应各个字母并相应进行自增操作

3、遍历ransomNote 字符串同样执行步骤2的操作但相应进行自减操作

4、判断如果数组元素小于0则直接返回false否则返回true

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
     int[] record=new int[26];
     if(ransomNote.length()>magazine.length())return false;
     for(int i=0;i<magazine.length();i++){
        int num=magazine.charAt(i)-'a';
        record[num]++;
     }
     for(int i=0;i<ransomNote.length();i++){
        int num=ransomNote.charAt(i)-'a';
        record[num]--;
        if(record[num]<0)return false;
     }
     return true;
    }
}