0

For example, given the following problem, what's the shortest way to implement a solution?

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.

Surely there's a better way than manually counting each character?

def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    c1, c2 = Counter(ransomNote), Counter(magazine)
    for letter in c1:
        if not (letter in c2 and c2[letter] >= c1[letter]):
            return False
        
    return True
Alec
  • 8,529
  • 8
  • 37
  • 63

3 Answers3

2

Indeed there is! Counter subtraction will yield a new Counter object containing only keys with positive values. If one item is a subset of another, the subtraction of the superset will yield an empty dictionary. That means that the following function can determine if any (hashable) "collection," including strings, is a subset of another

def isSubset(self, subset, superset) -> bool:
    return not Counter(subset) - Counter(superet)

In this case, the following one-liner would do

def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    return not Counter(ransomNote) - Counter(magazine)
Alec
  • 8,529
  • 8
  • 37
  • 63
1

Another Counter approach

from collections import Counter
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        a, b = Counter(ransomNote), Counter(magazine)
        return (a & b) == a
        # or return a.__iadd__(b).__eq__(a)
sahasrara62
  • 10,069
  • 3
  • 29
  • 44
  • upvoted, this is cool. I really like python's liberal use of these math/bitwise operators – Alec Feb 18 '23 at 00:11
  • @Alec just some new ways one learn when they do competitive programming :D, this has nothing to with production level code :p – sahasrara62 Feb 18 '23 at 00:16
0

Simple submultiset check:

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

Submitted at LeetCode, got accepted.

Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65