题目描述

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'

题解

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class L187重复的DNA序列 {
    public List<String> findRepeatedDnaSequences(String s) {
        int len=s.length(),sum=0,i=0;
        HashSet<String> ans = new HashSet<>();
        if(len<10)return new ArrayList<>(ans);
        HashSet<Integer> set = new HashSet<>();
        for (; i < 10; i++) {
            sum<<=2;
            sum+=toInt(s.charAt(i));
        }
        set.add(sum);
        for (; i < len; i++) {
            sum<<=2;
            sum+=toInt(s.charAt(i));
            sum&=0x0000fffff;
            if(set.contains(sum)){
                //从该位向前看九个 就重复了
                ans.add(s.substring(i-9,i+1));
            }else{
                set.add(sum);
            }
        }
        return  new ArrayList<>(ans);

    }
    public int toInt(char c){
        return switch (c){
            case 'A'->0;
            case 'C'->1;
            case 'G'->2;
            default -> 3;
        };
    }
    //以下是测试
    public void text() {
        List<String> a = findRepeatedDnaSequences("AAAAAAAAAAAAA");
        for (String s : a) {
            System.out.println(s);
        }
    }
    public static void main(String[] args) {
        new L187重复的DNA序列().text();
    }
}