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

解题思路

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组 record，来记录字符串 magazine 里每个字符出现的次数。

record 数组的大小为 26 就可以了，初始化为 0，因为字符 a 到字符 z 的 ASCII 也是 26 个连续的数值。

把字符映射到数组的下标上，因为字符 a 到字符 z 的 ASCII 是 26 个连续的数值，所以字符 a 映射为下标 0，相应的字符 z 映射为下标 25。

在遍历字符串 magazine 的时候，只需要将 magazine[i] - ‘a’ 所在的元素做 + 1 操作即可，并不需要记住字符 a 的 ASCII，只要求出一个相对数值就可以了。 这样就将字符串 magazine 中字符出现的次数，统计出来了。

之后检查字符串 ransomNote 中是否出现了这些字符，在遍历字符串 ransomNote 的时候，先判断 record 数组中对应索引处的值是否大于 0，如果不大于 0，说明 ransomNote 中出现了 magazine 中没有或者不足的字符，此时返回 false。

如果索引处的值大于 0，则只需要对 ransomNote[i] - ‘a’ 所在的元素做 - 1 操作即可。

最后如果 record 数组所有元素都为 0，说明字符串 s 和 t 是字母异位词，返回 true。

时间复杂度为 O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为 O(1)。

注意一开始就对比一下字符串长度，可以直接排除一些错误情况。

我的代码

public boolean canConstruct(String ransomNote, String magazine) {
    if (magazine.length() < ransomNote.length()) {
        return false;
    }
    int[] record = new int[26];

    for (int i = 0; i < magazine.length(); i++) {
        record[magazine.charAt(i) - 'a']++;// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
    }

    for (int i = 0; i < ransomNote.length(); i++) {
        if (record[ransomNote.charAt(i) - 'a'] > 0) {
            record[ransomNote.charAt(i) - 'a']--;
        } else {
            return false;
        }
    }
    return true;
}

时间复杂度：O(n)

空间复杂度：O(1)，因为定义是的一个常量大小的辅助数组

总结

数组就是简单的哈希表，但是数组的大小不是无限开辟的。

注意一开始就对比一下字符串长度，可以直接排除一些错误情况。

为什么要用数组，而不用 hashMap？

其实在本题的情况下，使用 hashMap 的空间消耗要比数组大一些的，因为 hashMap 要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！