187. 重复的DNA序列

题目

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 <= 10^5
s[i]==’A’、’C’、’G’ or ‘T’

思路

最直接的思路是记录每一个长度为的子串的个数，时间复杂度是#card=math&code=O%28n%2Am%29&id=EO2C5)，其中为长度，为子串的长度，题目中为。

可以优化一下，不直接记录字符串，因为比对字符串需要#card=math&code=O%28m%29&id=V7zUF)时间，而是将子串转化为哈希值，使用#card=math&code=RK%28Rabin-Karp%29&id=NE3Wn)字符串匹配算法，这里不对RK算法做详细说明了。时间复杂度为#card=math&code=O%28n%29&id=C3pvJ)。

官解的方法二很赞，使用了位运算，该方法和写法差异并不大，可以将核心的那一行代码换做位运算，变得看起来更优雅了一些。同样也是将看做四个数字，因此只需要两个比特就可以表示这四个字母，那么子串长度为就需要个比特，中的乘其实就是对应个比特左移两位，将最左面的那个字母移出去，然后将当前字母滑进来，对应位或运算，最后因为子串只有位，左边超出的要”截掉”，使用位与运算，不得不说很赞。

代码

RK算法(哈希表+滑窗)

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        if (n < 10) {
            return ans;
        }
        // key为哈希值，value为出现次数
        Map<Integer, Integer> map = new HashMap<>();
        // 将子串转化为整数，例如s=ACGAATTCCG，char转int后为0120033112，那么其对应的val就是 0*4^9 + 1*4^8 + 2*4^7 +...+ 2*4^0
        int val = 0;
        for (int i = 0; i < 10; i++) {
            val = val * 4 + char2int(s.charAt(i));
        }
        map.put(val, 1);
        int k = (int) Math.pow(4, 9);
        for (int i = 10; i < n; i++) {
            val = (val - k * char2int(s.charAt(i - 10))) * 4 + char2int(s.charAt(i));
            // 只在出现第二次时添加，避免重复添加
            if (map.getOrDefault(val, 0) == 1) {
                ans.add(s.substring(i - 9, i + 1));
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return ans;
    }
    // 将ACGT四个字母转化为数字
    int char2int(char c) {
        switch (c) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
        }
        return -1;
    }
}

哈希表+滑窗+位运算

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        if (n < 10) {
            return ans;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int val = 0;
        for (int i = 0; i < 10; i++) {
            // 左移两位对应RK中的乘4，位或对应RK中的+
            val = val << 2 | char2int(s.charAt(i));
        }
        map.put(val, 1);
        int k = (1 << 20) - 1;
        for (int i = 10; i < n; i++) {
            // 和(1 << 20) - 1位与是因为子串只需要20个比特，左边多出的要置0
            val = (val << 2 | char2int(s.charAt(i))) & k;
            if (map.getOrDefault(val, 0) == 1) {
                ans.add(s.substring(i - 9, i + 1));
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return ans;
    }
    int char2int(char c) {
        switch (c) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
        }
        return -1;
    }
}