当前位置：首页 > article >正文

Leetcode面试经典150题-383.赎金信

article 2024/9/29 15:56:40

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

一道超级简单的题，就名字比较唬人，自己看代码吧，实在看不懂就留言或者私信，第一时间解答

class Solution {
    /**赎金信是啥意思，完全不知道，但是看题意大概总结一下就是:magine里的每个字符只能使用一次，能不能组成ransomeNote 
    这啥破玩意，不就是magine里面含有ransomNote里的所有字符并且同一个字符的个数大于等于ransomeNote吗，整的挺吓人*/
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length() > magazine.length()) {
            /**你别我都长，我能包含你吗 */
            return false;
        }
        /**习惯性的转成字符数组方便操作 */
        char[] ransomNoteArr = ransomNote.toCharArray();
        char[] magazineArr = magazine.toCharArray();
        /**我们能想到的肯定是放在hashMap里看频率，但是哈希表的常数时间太大了
        又因为字符只包含小写字母，所以这里使用一个26长度int数组来代表哈希表就可以了 
        0位置表示a有多少个，1位置表示b有多少个，。。。25位置代表z有多少个*/
        int[] map = new int[26];
        /**先统计magazine里的字符的频次*/
        for(char c : magazineArr) {
            map[c-'a'] ++;
        }
        /**然后统计ransomNote里的字符频次，遇到就-1，如果某个字符出现了负数就返回false */
        for(char c : ransomNoteArr) {
            if(map[c-'a'] == 0) {
                return false;
            }
            map[c-'a'] --;
        }
        /**没有出现违反规则的返回true */
        return true;

    }
}