leetcode with python:383. Ransom Note

题目:

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.

给定一字串ransomNote和一字串magazine,判断ransomNote可否用magazine内的元素组成

这题其中一个解法是建立hashmap

class Solution:    def canConstruct(self, ransomNote: str, magazine: str) -> bool:        d1={}        d2={}        for i in ransomNote:            if i not in d1:                d1[i]=1            else:                d1[i]=d1[i]+1                        for i in magazine:            if i not in d2:                d2[i]=1            else:                d2[i]=d2[i]+1                        for i in d1:            if i not in d2:                return False            else:                if d2[i]<d1[i]:                    return False                        return True

用两个dictionary个别纪录两字串元素的出现次数
接着开始比较,若ransomNote的元素出现的次数比magazine的多
或者根本不在magazine内,就回传False
若无异常,则回传True
最后执行时间73ms(faster than 72.30%)

还有另外一个比较快的解法

class Solution:    def canConstruct(self, ransomNote: str, magazine: str) -> bool:        for i in ransomNote:            if i in magazine:                magazine=magazine.replace(i,"",1)            else:                return False                    return True

将ransomNote的元素一个一个拿出确认是否在magazine内
若存在则将magazine内的该元素消除一个
若不存在则回传False
迴圈执行结束后若无回传,则回传True
最后执行时间52ms(faster than 93.14%)

那我们下题见