O(m + n) time O(n) space, Using collections.Counter() in Python


  • 0
    A

    Check if every character c in the randomNote is in magazine. In order to search c efficiently in magazine,
    we create a dictionary that contains all the different characters in magazine as keys
    and theirs counts as values. This last step it is done using collections.Counter()

    from collections import Counter
    
    class Solution(object):
        def canConstruct(self, ransomNote, magazine):
            """
            :type ransomNote: str
            :type magazine: str
            :rtype: bool
            """
            # Create magazineDict as a hashTable of the form
            # (key, value) where key is a character in magazine
            # and value is an integer that represents its counts
            magazineDict = Counter(magazine)
            for c in ransomNote:
                if c not in magazineDict:
                    # c is not in the magazine
                    return False
                # c is in Magazine		
                if magazineDict[c] == 0:
                    # but not enough characters c
                    return False
                # magazine has enough c (so far), so we use one c
                magazineDict[c] -= 1
            # All the characters are in the magazine
            return True
    

    See also this post, an one-liner using Counter https://discuss.leetcode.com/topic/53902/o-m-n-one-liner-python


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.