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