Question

187. 重复的 DNA 序列

English Version

题目描述

DNA序列 由一系列核苷酸组成，缩写为

 'A', 'C', 'G' 和 'T'.。

• 例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

 

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

 

提示：

• 0 <= s.length <= 105
• s[i]=='A'、'C'、'G' or 'T'

解法

方法一：哈希表

我们定义一个哈希表 $cnt$，用于存储所有长度为 $10$ 的子字符串出现的次数。

遍历字符串 $s$ 的所有长度为 $10$ 的子字符串，对于当前子字符串 $t$，我们更新其在哈希表中对应的计数。如果 $t$ 的计数为 $2$，我们就将它加入答案。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n \times 10)$，空间复杂度 $O(n \times 10)$。其中 $n$ 是字符串 $s$ 的长度。

class Solution:
  def findRepeatedDnaSequences(self, s: str) -> List[str]:
    cnt = Counter()
    ans = []
    for i in range(len(s) - 10 + 1):
      t = s[i : i + 10]
      cnt[t] += 1
      if cnt[t] == 2:
        ans.append(t)
    return ans

class Solution {
  public List<String> findRepeatedDnaSequences(String s) {
    Map<String, Integer> cnt = new HashMap<>();
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < s.length() - 10 + 1; ++i) {
      String t = s.substring(i, i + 10);
      if (cnt.merge(t, 1, Integer::sum) == 2) {
        ans.add(t);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<string, int> cnt;
    vector<string> ans;
    for (int i = 0, n = s.size() - 10 + 1; i < n; ++i) {
      auto t = s.substr(i, 10);
      if (++cnt[t] == 2) {
        ans.emplace_back(t);
      }
    }
    return ans;
  }
};

func findRepeatedDnaSequences(s string) (ans []string) {
  cnt := map[string]int{}
  for i := 0; i < len(s)-10+1; i++ {
    t := s[i : i+10]
    cnt[t]++
    if cnt[t] == 2 {
      ans = append(ans, t)
    }
  }
  return
}

function findRepeatedDnaSequences(s: string): string[] {
  const n = s.length;
  const cnt: Map<string, number> = new Map();
  const ans: string[] = [];
  for (let i = 0; i <= n - 10; ++i) {
    const t = s.slice(i, i + 10);
    cnt.set(t, (cnt.get(t) ?? 0) + 1);
    if (cnt.get(t) === 2) {
      ans.push(t);
    }
  }
  return ans;
}

use std::collections::HashMap;

impl Solution {
  pub fn find_repeated_dna_sequences(s: String) -> Vec<String> {
    if s.len() < 10 {
      return vec![];
    }
    let mut cnt = HashMap::new();
    let mut ans = Vec::new();
    for i in 0..s.len() - 9 {
      let t = &s[i..i + 10];
      let count = cnt.entry(t).or_insert(0);
      *count += 1;
      if *count == 2 {
        ans.push(t.to_string());
      }
    }
    ans
  }
}

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function (s) {
  const cnt = new Map();
  const ans = [];
  for (let i = 0; i < s.length - 10 + 1; ++i) {
    const t = s.slice(i, i + 10);
    cnt.set(t, (cnt.get(t) || 0) + 1);
    if (cnt.get(t) === 2) {
      ans.push(t);
    }
  }
  return ans;
};

public class Solution {
  public IList<string> FindRepeatedDnaSequences(string s) {
    var cnt = new Dictionary<string, int>();
    var ans = new List<string>();
    for (int i = 0; i < s.Length - 10 + 1; ++i) {
      var t = s.Substring(i, 10);
      if (!cnt.ContainsKey(t)) {
        cnt[t] = 0;
      }
      if (++cnt[t] == 2) {
        ans.Add(t);
      }
    }
    return ans;
  }
}

方法二：Rabin-Karp 字符串匹配算法

本质上是滑动窗口和哈希的结合方法，和 0028.找出字符串中第一个匹配项的下标 类似，本题可以借助哈希函数将子序列计数的时间复杂度降低到 $O(1)$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。

func findRepeatedDnaSequences(s string) []string {
  hashCode := map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
  ans, cnt, left, right := []string{}, map[int]int{}, 0, 0

  sha, multi := 0, int(math.Pow(4, 9))
  for ; right < len(s); right++ {
    sha = sha*4 + hashCode[s[right]]
    if right-left+1 < 10 {
      continue
    }
    cnt[sha]++
    if cnt[sha] == 2 {
      ans = append(ans, s[left:right+1])
    }
    sha, left = sha-multi*hashCode[s[left]], left+1
  }
  return ans
}