383. 赎金信

leetcode链接：
https://leetcode.cn/problems/ransom-note/

方案一

先将一个字符串放到map中，然后另外一个去判断。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        Map<Character, Integer> magMap = new HashMap<>();

        for (char c : magazine.toCharArray()) {
            if (magMap.containsKey(c)) {
                magMap.replace(c, magMap.get(c) + 1);
            } else {
               magMap.put(c, 1);
            }
        }

        for (char c : ransomNote.toCharArray()) {
            if (magMap.containsKey(c)) {
                magMap.replace(c, magMap.get(c) - 1);
                if (magMap.get(c) < 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}

结果

解答成功:
执行耗时:11 ms,击败了22.91% 的Java用户
内存消耗:43.3 MB,击败了5.12% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( max(n, m) )

官方解答

– 与方案一相似，实现方法不同

https://leetcode.cn/problems/ransom-note/solution/shu-jin-xin-by-leetcode-solution-ji8a/

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;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/ransom-note/solution/shu-jin-xin-by-leetcode-solution-ji8a/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。