【LeetCode】16. RansomNode·赎金信

​活动地址：CSDN21天学习挑战赛

题目描述

英文版描述

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.

英文版地址

https://leetcode.com/problems/ransom-note/

中文版描述

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

中文版地址

https://leetcode.cn/problems/ransom-note/

解题思路

读取输入单词并遍历其字母，将读取到的字母存入集合，在便利第二个单词的时候，每读取到一个字母，查询集合中是否包含，有的话移除，没有直接返回false，直到第二个单词中的字母全部遍历完成，如果集合为空则返回true，否则返回false 由于magazine 中的每个字符只能在 ransomNote 中使用一次，所以使用list

解题方法

俺这版

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

官方版

 

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