LeetCode Top Interview 150) Ransom Note

Question

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.

Constraints:

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote and magazine consist of lowercase English letters.

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

---

---

소문자 알파벳으로 이루어진 두 문자열 ransomNote, magazine이 주어지고, ransomNote가 magazine을 이루는 문자만으로 만들어질수 있는지 여부를 bool값으로 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

from collections import defaultdict

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        d = defaultdict(int)
        for c in ransomNote:
            d[c] -= 1
        for c in magazine:
            d[c] += 1
        
        for val in d.values():
            if val < 0:
                return False
        return True

• 문자 : 등장횟수를 키값으로 가지는 딕셔너리 d를 정의합니다.
• ransomNote를 탐색하며 문자 등장횟수만큼 값을 빼줍니다.
• magazine을 탐색하며 문자 등장횟수만큼 값을 더합니다.
• d값을 탐색하며 음수가 남아있다면 False 모두 0이상이면 True를 반환합니다.
  • 음수가 남아있다는 것은 특정 문자가 ransomNote에서 더 많이 나왔기 때문에 magazine에서 더한 값이 0이상으로 올라오지 못했다는 의미입니다.

---

접근 방식도, 구현도 간단했던 문제입니다. 복잡하게 생각할 것 없이 각 문자열을 순회하고 결과도 순회하는 방식이였습니다.