[Leetcode] 383. Ransom Note (python)

#1.  문제

https://leetcode.com/problems/ransom-note/

Ransom Note - LeetCode

 

 

두 문자열  ransomeNote와 magazine이 주어질 때, magazine의 철자로 ransomeNote를 구성할 수 있는지 확인하는 문제

 

Input: 
ransomNote = "aab"
magazine = "baa"

Output: 
true

Explanation:
ransomNote 구성에 필요한 모든 철자를 magazine이 다 가지고 있음

 

 

---

#2.  풀이

 

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        import collections

        char_map = collections.defaultdict(int)

        for char in magazine:
            char_map[char] += 1  # magazine에서 철자 빈도수 확인하여 하나씩 올림, char_map 갱신

        for char in ransomNote:
            char_map[char] -= 1  # ransomNote에서 철자 빈도수 확인하여 하나씩 내림, char_map 갱신
            if char_map[char] < 0:  # 0 미만인 경우는 magazine이 유효한 철자를 가지고 있지 않다는 것
                return False

        return True

 

해시테이블로 쉽게 풀 수 있는 문제다.

magainze이 가진 철자 빈도수를 해시테이블에 업데이트하고, 이후 ransomeNote가 가진 char_map에 있는지 확인하여 있으면 -1씩 내려준다.

만약 해시테이블에서 0 미만의 값을 가지는 철자는 ransomNote에는 없다는 것이므로 False를 반환한다.