LEETCODE - 383. Ransom Note

❔핵심 문제

A 문자열이 변환된 B문자열의 substring인지 확인하는 문제이다.
예를 들어,
A = 'aa'
B = 'aba'이면
B가 a 2개를 가지고 있기 때문에 'aab'로 변환하면 A는 B의 substirng이 된다.

문제 해결법

예시 설명에서 알 수 있듯이 B 문자열의 각 알파벳 개수가, A 문자열의 상응하는 알파벳 개수보다 같거나 많으면 변환 가능하다고 볼 수 있다.

코드

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        alphabet_dict = dict()
        result = True
        # Count alphabets of magazine in terms of lexicon
        for alphabet in magazine:
            if alphabet not in alphabet_dict.keys():
                alphabet_dict[alphabet] = 1
            else:
                alphabet_dict[alphabet] += 1
        
        # Check
        for _alphabet in ransomNote:
            
            # If the alphabet does not exist or exceed the count
            if _alphabet not in alphabet_dict.keys() or alphabet_dict[_alphabet] == 0:
                result = False
                break
            else:
                alphabet_dict[_alphabet] -= 1
        
        return result

B 문자열의 알파벳 개수를 구한다.
이후 A 문자열의 상응하는 알파벳의 개수를 차감한다.
이 과정에서 B에 A 문자열의 알파벳이 없거나, 적게 가지고 있으면 False

🚀 리팩토링

Counter를 이용하면 손쉽게 구할 수 있다.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return not collections.Counter(ransomNote) - collections.Counter(magazine)

해당 코드에서 B 문자열이 변환 가능하면 return 값이
Counter()가 되는데 이것은 False로 평가된다.