【LeetCode刷题日记】383 赎金信

【摘要】 本文讲解了LeetCode 383题"赎金信"的哈希表解法。题目要求判断ransomNote字符串能否由magazine字符串中的字符构成（每个字符只能用一次）。解题思路：1. 使用长度为26的数组记录字符出现次数；2. 先遍历magazine统计字符频次；3. 再遍历ransomNote减少对应字符计数；4. 若任意字符计数为负则返回false。与242题"有效字母异位词"的区别在于本题是单向判断。关键点包括：字符不可重用、仅含小写字母、使用toCharArray()方法转换字符串为字符数组进行遍历。时间复杂度O(n)，空间复杂度O(1)。

题目背景：LeetCode 383

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 注意： 你可以假设两个字符串均只含有小写字母。 canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true

题目答案：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

题目解析：

这道题目和242.有效的字母异位词 很像，242.有效的字母异位词 相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。

然后需要注意的是：

本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。

• 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
• 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要

根据前面我们做这种相关题目的经验，我们先定义一个哈希映射数组，然后开始遍历后面的magazine，

   record[c - 'a'] += 1;

这步的意思就是记录magazine中存在的元素，存在一个就映射一个，

需要注意的：

toCharArray() 是干什么的：把字符串 变成 字符数组，方便用增强 for 循环一个个拿字符。

假如：

String str = "abc";

执行：

char[] arr = str.toCharArray();

结果：

arr 变成了 ['a', 'b', 'c']

就是 字符串 → 字符数组

然后接下来，我们遍历我们需要的ransom，加到同一个映射数组中，转成字符之后，如果存在，就在数组的相应位置自减，如果数组中有位置出现负数，则代表magazine中没有这个字母，因此才会变成负数。