# Solution by abdur

• #### 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.

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