赎金信[简单]

优质博文：IT-BLOG-CN

一、题目

给你两个字符串：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由小写英文字母组成

二、代码

【1】Map： 创建一个Map,key存放magazine字符，value存放count, 遍历ransomNote对count进行减小，如果小于0，说明不包含直接退出。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 创建一个Map, key 存放 magazine 字符，value存放count, 遍历 ransomNote 对 count进行减小，如果小于0，说明不包含
        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++) {
            int count = map.getOrDefault(ransomNote.charAt(i), 0);
            map.put(ransomNote.charAt(i), --count);
            if (count < 0) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度： O(m+n)其中m表示ransomNote的长度，n表示magazine的长度。
空间复杂度： O(m)其中m表示ransomNote的长度。

【2】字符统计： 如果字符串magazine的长度小于字符串ransomNote的长度，则我们可以肯定magazine无法构成ransomNote，此时直接返回false。首先统计magazine中每个英文字母a的次数cnt[a]，再遍历统计ransomNote中每个英文字母的次数，如果发现ransomNote中存在某个英文字母c的统计次数大于magazine中该字母统计次数cnt[c]，则此时我们直接返回false。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 创建一个26个字母长度的数组，下标表示字母，value表示个数
        int[] letter = new int[26];
        for (char c : magazine.toCharArray()) {
            letter[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            letter[c - 'a']--;
            if (letter[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度： O(m+n)其中m是字符串ransomNote的长度，n是字符串magazine的长度，我们只需要遍历两个字符一次即可。
空间复杂度： O(∣S∣)，S是字符集，这道题中S为全部小写英语字母，因此∣S∣=26。

【3】哈希表或数组： 我们可以用一个哈希表或长度为26的数组cnt记录字符串magazine中所有字符出现的次数。然后遍历字符串ransomNote，对于其中的每个字符c，我们将其从cnt的次数减1，如果减1之后的次数小于0，说明c在magazine中出现的次数不够，因此无法构成ransomNote，返回false即可。

否则，遍历结束后，说明ransomNote中的每个字符都可以在magazine中找到对应的字符，因此返回true。

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

时间复杂度： O(m+n)，其中m和n分别为字符串ransomNote和magazine的长度；
空间复杂度： O(C)，而C为字符集的大小，本题中C = 26；

【4】枚举： 把26字母中出现的字母全部统计一遍到数组中，然后遍历我们组成字符串（字符串转成字符数组），对出现的字母相减，减出来到最后，数组中没有出现小于0的数就是可以组成，相反不能组成

class Solution {
    public static boolean canConstruct(String ransomNote, String magazine) {
        int [] ans = new int[26];
        // 将字符串中的字符转换为字符数组
        for(char c : magazine.toCharArray()){
            // 26个字母 出现多少次
            ans[c-'a']++;
        }
        for (char c : ransomNote.toCharArray()){
            if(--ans[c - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
}