DEV Community

HHMathewChan

Posted on • Originally published at rebirthwithcode.tech

Python exercise 22: ransomnote

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

• 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

• Constraints:
• `1 <= ransomNote.length, magazine.length <= 105`
• `ransomNote` and `magazine` consist of lowercase English letters.

My Solution

• algorithm
``````>>determine if ransomNote can be constructed from magzine
set lengthr to length of ransomNote
set lengthm to length of magzine
if lengthr>lengthm:
return false
else:
for each char in ransomnote:
if char appear in magazine:
remove char in ransomenote
remove char in magazine
if lengthr equal to 0:
return True
else:
return False
``````
• key point

• need to split the question into case in terms of the difference between two string
• if length of ransomNote greater than length of magzine
• there is no way magzine have enough word to construct to the ransomNote
• code

``````class Solution:
def canConstruct(self,ransomNote: str, magazine: str) -> bool:
lenngthr = len(ransomNote)
lenngthm = len(magazine)
if lenngthr>lenngthm:
return  False
# lenngthr<=lenngthm
else:
for char in ransomNote:
if char in magazine:
# remove that char from both string
magazine=magazine.replace(char,"",1)
ransomNote=ransomNote.replace(char,"",1)
# This mean the whole string can be found on magzine
if len(ransomNote) == 0:
return True
# if ransomNote has not reduce to an empty string
else:
return False

``````

Other solution

``````class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
magazine_dict = {}
# constuct a dict with uniques as key and its occurance as value
for char in magazine:
if char not in magazine_dict:
magazine_dict[char] = 1
else:
magazine_dict[char] += 1
for char in ransomNote:
if char not in magazine_dict or magazine_dict[char] == 0:
return False
else:
magazine_dict[char] -= 1
# all char checked to be found on magazine_dict
return True
``````

My reflection

• I learn from others that when checking one group is belong to other group, use dictionary is faster.
• I do not understand why the solution should construct within a class but not a separate function.

Credit

challenge find on leet code 383