383. Ransom Note

Description

Given two strings ranosmNote 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 <= 10⁵
• ransomNote and magazine consist of lowercase English letters.

Submitted Code

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        if len(ransomNote) > len(magazine):   # ransomNote가 magazine보다 길다면 바로 False
            return False

        count = {}

        for l in ransomNote:
            count[l] = count.get(l, 0) + 1

        for l in magazine:
            if l in count and count[l] != 0:
                count[l] -= 1
        
        # 딕셔너리의 각 값이 0인지 확인하고 모두 0일 때만 True
        return True if all(v == 0 for v in count.values()) else False

Runtime: 19 ms | Beats 88.90%
Memory: 12.85 MB | Beats 15.54%

해시 테이블을 사용했다.

Other Solutions

1st

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

        for c in magazine:
            maga_hash[c] = 1 + maga_hash.get(c, 0)

        for c in ransomNote:
            if c not in maga_hash or maga_hash[c] <= 0:
                return False
            maga_hash[c] -= 1
        
        return True

time complexity: 𝑂(𝑛+𝑚)
space complexity: 𝑂(26 → 1)

ransomNote 대신 magazine의 원소와 출현 횟수를 해시 테이블에 저장하는 방법이 훨씬 더 깔끔한 것 같다.

2nd

from collections import Counter

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        st1, st2 = Counter(ransomNote), Counter(magazine)
        if st1 & st2 == st1:  # 교집합이 ransomNote와 동일할 경우 True
            return True
        return False

파이썬의 내장 모듈 collections.Counter은 각 문자의 출현 횟수를 자동으로 세어주는 딕셔너리이다. 또 Counter 객체끼리는 & 연산이 가능하기 때문에 편리하다.