python,set(),count()


  • 8
    V
    class Solution(object):
        def canConstruct(self, ransomNote, magazine):
            """
            :type ransomNote: str
            :type magazine: str
            :rtype: bool
            """
            for i in set(ransomNote):
                if ransomNote.count(i) > magazine.count(i):
                    return False
            return True
    

  • 0
    H

    @fanchao.cool Why is this solution so fast compared to collections.Counter? Isn't string.count O(n)?


  • 0
    C

    Any one can help me why this method is so fast (beat 95%)? count is O(N)? Thus, the total complexity should be O(N^2)?


  • 2

    @CTD I have the intuition that all the methods of the original data structure(set,list,dictionary and string) are implemented by c, so we can't run the code faster using iteration or other codes that we write ourselves. For example,if we want to find a certain element in a list, using the index method is quicker than we write an iteration code ourselves. I think that is probably why python can be used in machine learning now, because lots of methods in the module numpy and scipy are implementd by c.


  • 0
    S

    @CTD I think the complexity is O(n) because a dictionary is used as a data structure, like a string aaa, and the dictionary is like dict = {a:3} , so it takes O(1) to access the value . And the totally it is O(n)


Log in to reply
 

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