leetcode187. 重复的DNA序列

定长的滑动窗口加上哈希

def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        count = collections.defaultdict(int)
        l = 10
        res = []
        for i in range(len(s)-10+1):
            sub = s[i:i+l]
            count[sub] += 1
            if count[sub] == 2:
                res.append(sub)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

字符串匹配Rabin-Karp算法：
把要判断的字符串是否相等改变为其他的形式，来减少每次遍历这个子字符串的时间

def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = set()
        seen = set()
        RL = 4**9
        R = 4
        vis = {"A": 0, "C": 1, "G": 2, "T": 3}
        l = 0
        number = 0
        if len(s) < 10:
            return []
        for r in range(9):
            number = number * R + vis[s[r]]
        for r in range(9, len(s)):
            number = number * R + vis[s[r]]
            if number in seen:
                res.add(s[l:r + 1])
            else:
                seen.add(number)
            number = number - vis[s[l]] * RL
            l += 1
        return list(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25