題目敘述

題目敘述到我們有兩個字串 ransomNote 和 magazine

假設 ransomNote 可以透過 magazine 則回傳 True 否則我們回傳 False

解題思路

最簡單的方式莫過於我們使用兩個字典，一個 d1 和一個 d2 分別計算兩者字串出現過的次數

假設 ransomNote 的 d1 可以再每一個字元出現次數皆大於 magazine 的 d2 我們就回傳 True 否則我們回傳 False

當然，我們也可以只需要一個字典，怎麼做呢？

其實我們只需要 d1

然後我們用 d1 扣除遍歷 magazine 字元出現的次數，假設我們遍歷不到，就代表 ransomNote 無法構成 magazine

程式碼實作

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        d = defaultdict(int)

        for i in magazine:
            d[i] += 1

        for i in ransomNote:
            if i in d:
                d[i] -= 1
                if d[i] == 0:
                    del d[i]
            else:
                return False

        return True

時間與空間複雜度分析

• 時間複雜度（Time Complexity）：$O(len(ransomNote) + len(magazine))$

  • 兩個 loop 來遍歷兩字串的時間複雜度，所以是 $O(len(ransomNote) + len(magazine))$。

• 空間複雜度（Space Complexity）：$O(len(ransomNote))$

  • Dictionary 用來存 ransomNote 的空間。