Question
-
Given two strings
ransomNote
andmagazine
,- return
true
-
if
ransomNote
_can be constructed - by using the letters from_
magazine
andfalse
otherwise.
-
if
- return
Each letter in
magazine
can only be used once inransomNote
.
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
andmagazine
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
Top comments (0)