leetcode-solution/Python/0383-ransom-note.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# time complexity: O(n)
# space complexity: O(1)
from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomNoteCounter = Counter(ransomNote)
        magazineCounter = Counter(magazine)
        for key, freq in magazineCounter.items():
            if key in ransomNoteCounter:
                ransomNoteCounter[key] -= freq
                if ransomNoteCounter[key] <= 0:
                    del ransomNoteCounter[key]
        return len(ransomNoteCounter) == 0


ransomNote = "a"
magazine = "b"
print(Solution().canConstruct(ransomNote, magazine))
ransomNote = "aa"
magazine = "ab"
print(Solution().canConstruct(ransomNote, magazine))
ransomNote = "aa"
magazine = "aab"
print(Solution().canConstruct(ransomNote, magazine))