I get time limit exceeds for this simple code in python. But I guess it is O(n)? Similar algo in java works!


  • 0
    S
    class Solution(object):
    def findRepeatedDnaSequences(self, s):
        dicts = {}
        results = []
        for st in range(0,len(s)-9):
            k = s[st:st+10]
            if k not in dicts.keys():
                dicts[k]=1
            else:
                if k not in results:
                    results.append(k)
                    del dicts[k]
                
        return results

  • 1

    That's not O(n), only O(n^2). Because both k not in dicts.keys() and k not in results are only O(n), not O(1). Fixing the first one is trivial, just use k not in dicts. Appending .keys() there is just bad.


  • 0
    S

    God observation. I think I overlooked the fact that dicts.keys() returns a list and a list search is O(n). Thanks for taking time to reply. Cheers!


Log in to reply
 

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