DEV Community

HHMathewChan
HHMathewChan

Posted on • Originally published at rebirthwithcode.tech

3 1

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

Image of Docusign

🛠 Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs