题目链接

英文链接：https://leetcode.com/problems/repeated-dna-sequences/

中文链接：https://leetcode-cn.com/problems/repeated-dna-sequences/

题目详述

所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例:

1
2
3

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出: ["AAAAACCCCC", "CCCCCAAAAA"]

题目详解

方法一：运用哈希表。

截取出所有的长度为 10 的字符串，运用 HashMap 进行计数。
最后遍历 HashMap，将统计值大于 1 的字符串加入到结果集中。

public class LeetCode_00187 {

    public List<String> findRepeatedDnaSequences(String s) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 10; i <= s.length(); ++i) {
            String sub = s.substring(i - 10, i);
            map.put(sub, map.getOrDefault(sub, 0) + 1);
        }
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                res.add(entry.getKey());
            }
        }
        return res;
    }
}

方法二：运用位运算。

我们可以对上面每一次截取出字符串并统计的方式进行优化，采用位运算的方式来加快速度。
创建一个数组 f，定义 f['A'] = 0;、f['C'] = 1;、f['G'] = 2;、f['T'] = 3;。这样，对于 DNA 序列中的每一个字符，都可以运用 2 bit 来进行表示（0、1、2、3 这四个数只用两位即可表示）。
通过 << 和 | 操作，对于长度为 10 的字符串，我们可以得到一个 20 bit 的整数（第一个字符用最高两位表示，最后一个字符用最低两位表示）。这个整数可以用来代表这个字符串。这样判断当前字符串是否在之前出现过，就变成了判断对应的这个整数是否在之前出现过。运用 BitSet 进行判断再合适不过了。
创建两个 BitSet vis 和 add，vis 用来判断字符串是否在之前出现过，add 用来判断字符串是否已经加入到结果集中。
遍历字符串序列，首先加入 9 个字符，从第十个字符开始，执行以下操作
执行 v = (v << 2) & 0xfffff | f[cs[i]];，v << 2 代表把之前的位左移；& 0xfffff 去除前面多余的位，使这个数维持在 20 位（即代表一个长度为 10 的字符串）；| f[cs[i]] 加上当前字符所代表两位。这样最终得到的整数 v 就代表了当前字符串。
对于 v，若之前出现过（vis.get(v) 为真），说明满足条件，但是还要判断当前字符串之前是否已经加入到结果集中。
- 若之前没有添加过，需要将当前字符串加入到结果集中，并设置添加标志。
- 若之前添加过，显然不用再添加。
对于 v，若之前未出现过，则设置 vis.set(v); ，代表现在出现了。

public class LeetCode_00187 {

    public static List<String> findRepeatedDnaSequences(String s) {
        if (s.length() <= 10) {
            return new ArrayList<>();
        }
        char[] cs = s.toCharArray();
        int n = cs.length;
        byte[] f = new byte[85];
        f['A'] = 0;
        f['C'] = 1;
        f['G'] = 2;
        f['T'] = 3;
        BitSet vis = new BitSet();
        BitSet add = new BitSet();
        List<String> res = new ArrayList<>(n >> 1);
        int v = 0;
        for (int i = 0; i < 9; ++i) {
            v = (v << 2) | f[cs[i]];
        }
        for (int i = 9; i < n; ++i) {
            v = (v << 2) & 0xfffff | f[cs[i]];
            if (vis.get(v)) {
                if (!add.get(v)) {
                    res.add(String.valueOf(cs, i - 9, 10));
                    add.set(v);
                }
            } else {
                vis.set(v);
            }
        }
        return res;
    }
}