[Leetcode/파이썬] 383. Ransom Note

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

 

Constraints:

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

 

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine) :
            return False
            
        hashTable = {}
        for maga in magazine :
            hashTable[maga] = 1 + hashTable.get(maga, 0)
            
        for ransom in ransomNote :
            if ransom not in hashTable or hashTable[ransom] <= 0 :
                return False

            hashTable[ransom] -= 1
        
        return True

magazine 에 있는 글자들을 카운팅 한 후 ransomNote 의 글자들과 비교하면서 카운팅을 한다.

만약 ransomNote 에 있는 글자 ransom 이 hashTable 에 없거나 0 이하의 숫자이면(==0 이라고 해도 된다) False 를 리턴, ransomNote의 글자가 모두 들어있다면 마지막에 True를 리턴해 준다.

문제를 보다 보니, ransomNote의 글자수가 magazine보다 많으면 애초에 문제가 해결되지 않기 때문에, 가장 위에 가지치기 형식으로 넣어두었다.