1. Problem
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.
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
Constraints:
- 1 <= ransomNote.length, magazine.length <= 105
- ransomNote and magazine consist of lowercase English letters.
2. Solution
2.1. Using dictionary
I solve this problem like this. I count magazine character count using dictionary. And i subtract dictionary’s count while looping through the for statement.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
dic = {}
if len(ransomNote) > len(magazine):
return False
# make dic using magazine
for m in magazine:
if dic.get(m, 0):
dic[m] += 1
else:
dic[m] = 1
# check ransomNote can made by magazine
for r in ransomNote:
if r not in dic:
return False
if dic[r] == 0:
return False
dic[r] -= 1
return True
2.2. Using Counter
I confirmed other user’s solution.
If we use Counter class on “hello world”, we can get under value.
>>> Counter("hello world")
Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})
We can solve this problem like under code.
class Solution(object):
def canConstruct(self, ransomNote, magazine):
st1, st2 = Counter(ransomNote), Counter(magazine)
if st1 & st2 == st1:
return True
return False