Python O(n) solution

  • 0
    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):
            for i in range(l1):
                if ransomNote[i] in s:
                    c += 1
            if c == l1:
                return True
                return False

  • 1

    @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.