LeetCode 383. Ransom Note - Python

'383. Ransom Note'는 문자열 ransomNote가 문자열 magazine이 가진 문자로 만들 수 있는지 판별하는 문제이다.

---

문제

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.

---

풀이 1

magazine의 문자들은 ransomNote에 한 번씩만 사용될 수 있다. 예를 들어 ransomNote에 e가 두 번 포함되어 있으면 magazine에는 e가 최소 두 개 이상 포함되어 있어야만 참이 될 수 있다.

이 문제의 풀이는 Counter를 이용하면 한 줄로 쓸 수 있다.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return Counter(ransomNote) <= Counter(magazine)

collections 모듈의 Counter 클래스를 이용한 풀이

---

풀이 2

한 줄로 풀리니까 뭔가 재미가 없어서 써 본, 내가 Counter의 존재를 몰랐다면 적었을 풀이. 

magazine의 문자들의 개수를 센 dictionary를 만들고, ransomNote에 그 문자가 등장할때마다 한 개씩 빼준다.

ransomNote의 문자를 순회할 때, 그 문자가 dictionary의 key에 존재하지 않거나 그에 대한 value가 0이면 False를 return한다.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # the number of usable characters
        chars = {}
        
        for letter in magazine:
            chars[letter] = chars.get(letter, 0) + 1
        
        for letter in ransomNote:
            if letter in chars and chars[letter]:
                chars[letter] -= 1
            else:
                return False
        
        return True

dictionary를 이용한 풀이