DEV Community

HHMathewChan
HHMathewChan

Posted on • Originally published at rebirthwithcode.tech

Python exercise 22: ransomnote

#beginners #python #leetcode

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
Enter fullscreen mode Exit fullscreen mode

  • 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)