A simple python algorithm with dictionary 148ms


  • 0
    A
    class Solution:
        # @param {string} s
        # @return {string[]}
        def findRepeatedDnaSequences(self, s):
            if s is None:
                return []
    
            s_len = len(s)
            if s_len<=10:
                return []
    
            mid_res = {}
            res = []
    
            for i in range(s_len-10+1):
                subs = s[i:i+10]
                val = mid_res.get(subs)
                if val is None:
                    mid_res[subs] = 0
                else:
                    if val == 0:
                        res.append(subs)
                        mid_res[subs] += 1
    
            return res

  • 0
    G

    Here is my code, similar idea but much easier to read :)

    class Solution:
    	# @param {string} s
    	# @return {string[]}
    	def findRepeatedDnaSequences(self, s):
    		if len(s) < 11:
    			return []
    		pool = set()
    		ans = set()
    		for i in range(len(s)-9):
    			currstr = s[i:i+10]
    			if currstr not in pool:
    				pool.add(currstr)
    			else:
    				ans.add(currstr)
    		return list(ans)

Log in to reply
 

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