題目:

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%)

那我們下題見