Solution by abdur


  • 0
    A

    Approach #1 Brute Force [Accepted]

    Intuition

    For every letter in the magazine, see if the corresponding letter exists in the ransom note. If it does, go ahead and delete the letter from the ransom note.

    Our function will return true only if, after the above process, the ransom note is now empty

    Algorithm

    Python

    def canConstruct(self, ransomNote, magazine):
            """
            :type ransomNote: str
            :type magazine: str
            :rtype: bool
            """
    
            # to handle edge case
            if ransomNote == "":
                return True
            
            for i in magazine:
                p = ransomNote.find(i)
                s = ""
                if p != -1:
                    s = ransomNote[:p]
                if p != len(ransomNote) - 1:
                    s += ransomNote[p+1:]
                if len(s) == 0:
                    return True
                ransomNote = s
            return False
    

    Complexity Analysis

    Let's say that 'm' is the length of the ransomNote and 'n' is the length of the magazine.

    • Time complexity : $$O(n*m)$$.

    For every character in the magazine, we search in the ransomNote ( or vice versa ) - hence, similar to a nested loop, the complexity is $$O(n*m)$$.

    • Space complexity : $$O(1)$$.

    Approach #2 Using a counter [Accepted]

    Intuition

    Instead of searching everytime, it would be helpful if we just find out how many unique characters are there in the ransomNote and how many times each character is needed. Then we can also see how many times the particular character occurs in the magazine.

    Our function will return true only if, for every character in the ransomNote, the same character occurs in the magazine, with an equal or higher frequency

    Algorithm

    Consider a dictionary, which will store the number of times all characters in a string have occurred. We will construct one from the note and one from the magazine. Check if the letters from the note are present in the magazine, with the help of your 'counter' dictionary and if present, the number of times they are in the magazine is more or equal to that in the note.

    Python

    def canConstruct(self, ransomNote, magazine):
            magazineCounter = {}
            ransomNoteCounter = {}
            for i in magazine:
                magazineCounter[i] = magazineCounter.get(i,0)+1
            for i in ransomNote:
                ransomNoteCounter[i] = ransomNoteCounter.get(i,0)+1
            for i in ransomNoteCounter.keys():
                if(magazineCounter.get(i,0) < ransomNoteCounter[i]):
                    return False
            return True
    

    Complexity Analysis

    • Time complexity : $$O(n+m+m) = O(max(n, m))$$. Everything we do here is done in one iteration - going over both the notes, and then going over the keys of the ransomNote again. As a dictionary lookup is approximately $$O(1)$$, the overall complexity is $$O(max(m + n))$$.

    • Space complexity : $$O(max(m, n))$$. There are two dictionaries here, and each can, in the worse case, have a size of $$m$$ and $$n$$, if all of them no repeating characters.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.