DEV Community

HHMathewChan
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
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)