題目出處

383. Ransom Note

難度

easy

題目分類

Hash table, string, counting

個人範例程式碼

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ran_dict = Counter(ransomNote)
        mag_dict = Counter(magazine)

        for idx, ele in enumerate(ran_dict.keys()):
            if ele not in mag_dict:
                return False # not found
            elif ran_dict[ele] > mag_dict[ele]:
                return False # not enough
            else:
                pass
        return True

Time Complexity

O(n)

Space Complexity

x

算法說明

這題本身不難，還可以體驗一下 python Counter 的強大之處。

練習一下 string 怎麼 parse，for char in string，
即可「一個一個 char」的把「string」內容一個一個字提取出來。

此外，python collection 內建的 Counter function，
快速幫我們把計算數量的 hash dictionary 完成了。

如果還不知道 python Counter 用法的，「強烈建議」一定要會，寫程式效率會快超級多！！！
可參考我的另外一篇文：
【Python】python counter() 用法整理 – 快速計算資料內容的數量

我們就不用再另外寫 hash table 做 count 的動作了。

corner case 特殊情況處理

• 處理「不存在」值的情況
• 處理「不足夠」值的情況

Boundary conditions/ Edge conditions 邊際情況處理

x

Reference