Why python dict TLE but set AC


  • 0
    H

    AC code:

    class Solution:
    def convert(self,s):
    maps={'A':1,'C':2,'G':3,'T':4}
    num=0
    for i in s:
    num+=maps[i]
    num<<=3
    num>>=3
    return num

    def findRepeatedDnaSequences(self, s):
        res=[]
        resmap=set([])
        repeatmap=set([])
        idx=0
        tmps=[]
        for i in range(len(s)):
            if s[i:(i+10)] in repeatmap:
                continue
            tmp=self.convert(s[i:(i+10)])
            if tmp in resmap:
                repeatmap.add(s[i:(i+10)])
                res.append(s[i:(i+10)])
            else:
                resmap.add(tmp)
        return res
    

    TLE code, only difference is set changed to dict:

    class Solution:
    def convert(self,s):
    maps={'A':1,'C':2,'G':3,'T':4}
    num=0
    for i in s:
    num+=maps[i]
    num<<=3
    num>>=3
    return num

    def findRepeatedDnaSequences(self, s):
        res=[]
        resmap={}
        repeatmap={}
        idx=0
        tmps=[]
        for i in range(len(s)):
            if s[i:(i+10)] in repeatmap.keys():
                continue
            tmp=self.convert(s[i:(i+10)])
            if tmp in resmap.keys() :
                if tmp not in repeatmap.keys():
                    repeatmap[s[i:(i+10)]]=True
                    res.append(s[i:(i+10)])
            else:
                resmap[tmp]=True
        return res

  • 1
    O

    you should use "xxx in dict" instead of "xxx in dict.keys()"


  • 0
    H

    Big thanks, AC now


Log in to reply
 

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