跳到主要内容

187.重复的DNA序列

链接：187.重复的DNA序列
难度：Medium
标签：位运算、哈希表、字符串、滑动窗口、哈希函数、滚动哈希
简介：编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

题解 1 - typescript​

  • 编辑时间：2021-07-24
  • 执行用时：92ms
  • 内存消耗：50.4MB
  • 编程语言：typescript
  • 解法介绍：遍历所欲子串。
function findRepeatedDnaSequences(s: string): string[] {
  const set = new Set<string>();
  const ans = new Set<string>();
  for (let i = 0, l = s.length; i <= l - 10; i++) {
    const subStr = s.substr(i, 10);
    if (set.has(subStr)) ans.add(subStr);
    else set.add(subStr);
  }
  return [...ans];
}

题解 2 - typescript​

  • 编辑时间：2021-10-08
  • 执行用时：128ms
  • 内存消耗：52.1MB
  • 编程语言：typescript
  • 解法介绍：滑动窗口。
function findRepeatedDnaSequences(s: string): string[] {
  const set = new Set<string>();
  const window = s.substr(0, 10).split('');
  set.add(window.join(''));
  const ans = new Set<string>();
  for (let i = 10, l = s.length; i < l; i++) {
    window.shift();
    window.push(s[i]);
    const str = window.join('');
    if (set.has(str)) ans.add(str);
    set.add(str);
  }
  return [...ans];
}

题解 3 - typescript​

  • 编辑时间：2021-10-08
  • 执行用时：80ms
  • 内存消耗：50.6MB
  • 编程语言：typescript
  • 解法介绍：滑动窗口。
function findRepeatedDnaSequences(s: string): string[] {
  const set = new Set<string>();
  let str = s.substr(0, 10);
  set.add(str);
  const ans = new Set<string>();
  for (let i = 10, l = s.length; i < l; i++) {
    str = str.substring(1) + s[i];
    if (set.has(str)) ans.add(str);
    set.add(str);
  }
  return [...ans];
}

题解 4 - python​

  • 编辑时间：2023-11-05
  • 执行用时：80ms
  • 内存消耗：28.48MB
  • 编程语言：python
  • 解法介绍：哈希存储。
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        res = []
        m = Counter()
        for i in range(len(s) - 9):
            subs = s[i: i + 10]
            m[subs] += 1
            if m[subs] == 2: res.append(subs)
        return res