383.Ransom_Note_(Easy).md

383. Ransom Note (Easy)

Date and Time: Jun 5, 2024, 11:56 PM (EST)
Update: Jul 15, 11:30 AM (EST)

Link: https://leetcode.com/problems/ransom-note/

Question:

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

My Solution:

This new refined version only uses words{} to store all elements and its counts. Then in ransomNote we check if i exists in words{} or not (return False), otherwise, we decrement the counts and if words[i] == 0, we can delete the word.

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

Time Complexity: $O(\text{len(ransomNote)} + \text{len(magazine)})$, because we loop over ransomNote, magazine.
Space Complexity: $O(\text{len(magazine)})$, because we only store elements in magazine.