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(target) 和 magazine(dict) 拼字，如果拼得出來=True，反之為 False。
測試案例
Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
思路
- 根據規則每個字只能用一次，如果重複使用則返回 False
- 創建 hashmap 儲存 magazine values
- loop 依序遞減
解法
def canConstruct(self, ransomNote: str, magazine: str):
values = {}
for c in magazine:
if c not in values: # 不存在 hashmap 內
values[c] = 1 # 建立
else:
values[c] += 1 # 有則+1
for c in ransomNote:
if c not in values or values[c] == 0: # 不存在或已經用完
return False
else:
values[c] -= 1 # 有則-1
return True
使用內建 defaultdict 來處理 hashmap，解法大同小異，但速度較快且代碼更簡潔。
from collections import defaultdict
def canConstruct(self, ransomNote: str, magazine: str):
values = defaultdict(int) # 設定預設值為 0
for c in magazine:
values[c] += 1 # 建立
for c in ransomNote:
if c not in values or values[c] == 0: # 不存在或已經用完
return False
else:
values[c] -= 1 # 有則-1
return True