O(m+n) with m and n being the lengths of the strings.
def canConstruct(self, ransomNote, magazine):
return not collections.Counter(ransomNote) - collections.Counter(magazine)
@StefanPochmann Very nice, but what does the operator not over a dictionary? I image return False if there exists any negative value?
@astudillor It returns True if and only if the dictionary is empty. However, the subtraction operator keeps only positive values, so not
here essentially means “return False if there are any positive values”. But since we're subtracting magazine from ransomNote, any positive value would be negative if we were subtracting ransomNote from magazine (which makes much more sense intuitively). Any negative count in such subtraction means we spent more letters than available, so we return False.
Because of all that confusion, even though this solution is incredibly concise, I'd rather solve it in a more direct way:
c = Counter(magazine)
c.subtract(Counter(ransomNote))
return all(v >= 0 for v in c.values())
@Derek_Han No, there is no such thing in Java, at least not in the standard library, so your best bet is to use a Map with getOrDefault and a few loops. On the other hand, it's very easy to get full Unicode support in Java, including non-BMP characters, which would be tricky in Python.