首页 > itarticle > 算法笔记: 力扣#383 赎金信

算法笔记: 力扣#383 赎金信

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        counter = dict()
        for c in magazine:
            counter[c] = counter.get(c, 0)+1
        for c in ransomNote:
            if not counter.get(c, 0):
                return False
            counter[c] -= 1
        return True

Java 实现

class  {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> counter = new HashMap<>();
        for(char c : magazine.toCharArray()){
            counter.put(c, counter.getOrDefault(c, 0)+1);
        }
        for(char c : ransomNote.toCharArray()){
            int freq = counter.getOrDefault(c, 0);
            if(freq==0){ return false; }
            counter.put(c, freq-1);
        }
        return true;
    }
}

时间复杂度

O(n).

空间复杂度

O(1).

链接

383. Ransom Note
383. 赎金信
 (English version) Algorithm Notes: Leetcode#383 Ransom Note