[leetcode] 383. Ransom Note _ Algorithm Problem Solve for python

1. Problem

383. Ransom Note

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


  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.

2. Solution

2.1. Using dictionary

I solve this problem like this. I count magazine character count using dictionary. And i subtract dictionary’s count while looping through the for statement.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dic = {}

        if len(ransomNote) > len(magazine):
            return False

        # make dic using magazine
        for m in magazine:
            if dic.get(m, 0):
                dic[m] += 1
                dic[m] = 1

        # check ransomNote can made by magazine
        for r in ransomNote:
            if r not in dic:
                return False

            if dic[r] == 0:
                return False
            dic[r] -= 1

        return True

2.2. Using Counter

I confirmed other user’s solution.

If we use Counter class on “hello world”, we can get under value.

>>> Counter("hello world")
Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

We can solve this problem like under code.

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        st1, st2 = Counter(ransomNote), Counter(magazine)
        if st1 & st2 == st1:
            return True
        return False