LeetCode 187 重复的DNA序列
- 题目描述
- 解题思路

LeetCode 187 重复的DNA序列

https://leetcode-cn.com/problems/repeated-dna-sequences/

题目描述

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

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

提示：

0 <= s.length <= 10^5
s[i] 为 ‘A’、’C’、’G’ 或 ‘T’

解题思路

哈希表

一边遍历子串一边比较并记录当前序列

class Solution {

    static final int L = 10;

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(NL)，其中 N 是字符串 s 的长度，L=10 即目标子串的长度。

空间复杂度：O(NL)。

哈希表+滑动窗口+位运算

A：00，B：01，C：10，D：11
设当前滑动窗口对应的整数表示为 x，当我们要计算下一个子串时，就将滑动窗口向右移动一位
- 此时会有一个新的字符进入窗口，以及窗口最左边的字符离开窗口

class Solution {
    static final int L = 10;
    Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        int n = s.length();
        if (n <= L) {
            return ans;
        }
        int x = 0;
        for (int i = 0; i < L - 1; ++i) {                    // 初始化窗口
            x = (x << 2) | bin.get(s.charAt(i));
        }
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int i = 0; i <= n - L; ++i) {   // 窗口右移
            // 左移+或运算：新的字符进入窗口                  与运算：窗口最左边的字符离开窗口
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            if (cnt.get(x) == 2) {
                ans.add(s.substring(i, i + L));
            }
        }
        return ans;
    }
}

复杂度分析

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

字符串哈希+前缀和

Java 中的 String 的 hashCode 实现是会对字符串进行遍历的，这样哈希计数过程仍与长度有关，而 Integer 的 hashCode 就是该值本身，这是与长度无关的。
要实现真正的O(N)时间复杂度，要用Integer（hash结果本身）作为hashCode。
- 哈希数组 h[]：存放hashCode前缀和
- 次方数组 p[]：表示相差的位数

class Solution {
    int N = (int)1e5+10, P = 131313;
    int[] h = new int[N], p = new int[N];
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * P + s.charAt(i - 1);                    // 计算前缀和
            p[i] = p[i - 1] * P;                                    // 存放次方
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i + 10 - 1 <= n; i++) {
            int j = i + 10 - 1;
            int hash = h[j] - h[i - 1] * p[j - i + 1];                // 计算s中i到j位置子串对应的hashCode
            int cnt = map.getOrDefault(hash, 0);
            if (cnt == 1) ans.add(s.substring(i - 1, i + 10 - 1));
            map.put(hash, cnt + 1);
        }
        return ans;
    }
}

数组+位运算

使用字符数组比不断对字符串进行切分速度要快
使用数组来替代hashmap，速度更快

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int len = s.length();
        List<String> ans = new ArrayList<String>();
        if (len < 11) {
            return ans;
        }
        char[] cs = s.toCharArray();            // 字符数组
        int cur = 0;
        for (int i = 0; i < 10; i++) {            // 初始化窗口，第一串的值为cur
            cur = (cur << 2) | map(cs[i]);
        }
        int cut = 0b11111111111111111111;
        Boolean[] table = new Boolean[cut + 1];    //  
        table[cur] = false;
        for (int i = 10; i < len; i++) {
            cur = ((cur << 2) | map(cs[i])) & cut;
            Boolean has = table[cur];
            if (has == null) {
                table[cur] = false;
            } else if (!has) {
                ans.add(new String(cs, i - 9, 10));
                table[cur] = true;
            }
        }
        return ans;
    }

    private int map(char c) {
        if (c == 'A') {
            return 0b00;
        }
        if (c == 'C') {
            return 0b01;
        }
        if (c == 'G') {
            return 0b10;
        }
        if (c == 'T') {
            return 0b11;
        }
        return -1;
    }
}

算法从入门到入土

2021/10/15 LeetCode 187 重复的DNA序列