Python O(n) solution


  • 0
    X
    class Solution(object):
        def canConstruct(self, ransomNote, magazine):
            """
            :type ransomNote: str
            :type magazine: str
            :rtype: bool
            """
            l1 = len(ransomNote)
            l2 = len(magazine)
            c = 0
            s = []
            for j in range(l2):
                s.append(magazine[j])
            for i in range(l1):
                if ransomNote[i] in s:
                    s.remove(ransomNote[i])
                    c += 1
            if c == l1:
                return True
            else:
                return False
    

  • 1
    T

    @xiaohan3 I think your algorithm is not O(n), dude. "in" and "remove" over lists are O(n) in python. Let's say n is the size of ransomNote and m the size of magazine, the code below is O(n*m):

        for i in range(l1): # O(n)
            if ransomNote[i] in s:  # O(m)
                s.remove(ransomNote[i]) # O(m)

Log in to reply
 

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