unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 383: Ransom Note

link

We should find all characters of the ransomNote in the magazine. So, we use two passes: (1) For the magazine, build {char -> count} map (2) For each char in ransomNote, we try finding it in magazine.

Say magazine has n chars and ransomNote has m chars.

Time: \mathcal{O}(n + m), space: \mathcal{O}(\texttt{alphabet-size}).

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        mag = {}
        for c in magazine:
            mag[c] = mag.get(c, 0) + 1
        
        for c in ransomNote:
            if mag.get(c, 0) == 0:
                return False
            mag[c] -= 1
        
        return True

tanvirdotzaman

,

Leave a comment