[Top Interview 150] 383. Ransom Note

Solution)

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magDic = {}

        for char in magazine:
            if char in magDic:
                magDic[char] += 1
            else:
                magDic[char] = 1
        

        for char in ransomNote:
            if char in magDic:
                magDic[char] -= 1

                if magDic[char] == 0:
                    del magDic[char]
            
            else:
                return False
        
        return True

 
Problem: LeetCode
 
Time Complexity: O(m+n)
Space Complexity: O(m)

Explanation)

I think this problem can be solved using two pointers, which would allow us to save some memory space.
However, the problem was categorized under hashmap, so I used dictionary.
 
I first iterated through magazine and recorded the frequencies of the characters in a dictionary. Then I iterated through ransomNote and checked if the characters existed in the dictionary. 

Initialization)

Let's first define a dictionary that will store the characters of magazine.
 

def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magDic = {}

magazine iteration)

While we iterate through magazine, we'll record the frequencies of its characters.
 
If a character already exists in the dictionary, we'll increment its value by 1.
If a character does not exist in the dictionary, we'll add the character to the dictionary and set its value to 1.
 

def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magDic = {}

        for char in magazine:
            if char in magDic:
                magDic[char] += 1
            else:
                magDic[char] = 1

ransomNote iteration)

After we recorded all the characters of magazine in magDic, we'll iterate through ransomNote and see if its character exists in magDic. 
 
As we iterate ransomNote, we'll check if its character exists in magDic.
 
If it does exist, we'll decrement the value by 1. After the decrement, if the value becomes zero, we'll get rid of the character out of magDic. 
If it doesn't exist, that means ransomNote cannot be constructed using letters in magazine. Thus we'll return False.
 
If the iteration is done without returning False, that means ransomNote can be constructed using letters in magazine. Thus we'll return True.
 

def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magDic = {}

        for char in magazine:
            if char in magDic:
                magDic[char] += 1
            else:
                magDic[char] = 1
        

        for char in ransomNote:
            if char in magDic:
                magDic[char] -= 1

                if magDic[char] == 0:
                    del magDic[char]
            
            else:
                return False
        
        return True

 
 
Whether it's a job that you enjoy or not, it's hard to keep up the consistent work. Especially when you're stuck in a turbulence. But I'll always try my best to keep up with it :)