【哈希表, 滑动哈希】重复的DNA序列「滑动哈希基础」

题目

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'

解题

方法一：哈希表

思路

维护一个哈希表记录 s 所有长度为 10 的字串的出现频率，把所有出现频率为两次的 10 长度字串加入结果集合中。

代码

class Solution {
    private static final int SUB_LEN = 10;

    public List<String> findRepeatedDnaSequences(String s) {
        Map<String, Integer> frequencies = new HashMap<>();
        List<String> ans = new ArrayList<>();
        for (int i = 0; i + SUB_LEN <= s.length(); i++) {
            String sub = s.substring(i, i + SUB_LEN);
            int count = frequencies.getOrDefault(sub, 0);
            if (++count == 2) {
                ans.add(sub);
            }
            frequencies.put(sub, count);
        }
        return ans;
    }
}

时间复杂度：$O(10n)$

方法二：滑动哈希

思路

滑动窗口+滑动哈希。

滑动哈希

首先来探讨两个问题：

1. 给定一个十进制整数，如何在其最低位上添加一位数字？

   很简单，只需要把该数乘以 $10$ 再加上那位数字即可，例：

   • 给定 $n = 123456$ ，在其最低位上添加 $x = 7$：
     $n \times 10 + x = 1234560 + 7 = 1234567$ 就是答案。

   那么推广一下：给定一个 $R$ 进制的数 $n$，在其最低位上添加一位数字 $x$ 的方法是：

   • $n = n \times R + x$。

2. 给定一个十进制整数，如何从其最高位上删除一位数字？

   同样很简单，只需要把该数减去 那位数字乘以「$10$ 的「该数的位数减一」次方即可」，例：

   • 给定 $n = 654321$ ，需要删除其最低位的 $x = 6$：
     $n - x \times 10 ^ {len(n) - 1} = 654321 - 600000 = 54321$ 就是答案。

   那么推广一下：给定一个 $R$ 进制长度为 $L$ 的数 $n$，在其最高位上删除一位数字 $x$ 的方法是：

   • $n = n - x \times R ^ {L - 1}$。

以上就是滑动哈希的核心原理了。

接下来以本题为例继续理解滑动哈希：

本题是想让我们在字符串 s 中找出长度为 $10$ 且重复出现的子字符串（字符串中只会出现 'A'、'C'、'G'、'T'）。

除了上面暴力枚举所有长度为 10 的子字符串然后放入哈希表判重的方法，我们还可以维护一个长度为 $10$ 的滑动窗口，不断右移窗口并把窗口转成字符串加入哈希表进行判重，但是这样还是要把窗口转成字符串，时间复杂度依旧没有降低。

如何才能在不生成字符串的情况下给字符串判重呢？
答案是：把 AGCT 四种字符分别映射为 0123 四个数字，那么长度为 $10$ 的子字符串就可以看作一个「$10$ 位的 $4$ 进制数字」，该数字可以唯一标识一个字符串，这样以来滑动窗口的移动就可以看作是在该数的最低位增加数字或在其最高位删除数字了，根据之前给出的两个公式，窗口滑动以及哈希查找的时间复杂度可以降低到 $O(1)$。并且字符串生成的哈希数最大为 $4^{10} < 2^{32}-1$ ，也就是说 int 整形就可以存下。

整理如下：

// 把四种字符映射为数字
MAP = {'A': 0, 'C': 1, 'G': 2, 'T': 3};
// 滑动窗口扩大
windowHash = windowHash * R + nums[right++];
// 滑动窗口缩小
windowHash = windowHash - nums[left++] * RL;

参考：滑动窗口算法延伸：Rabin Karp 字符匹配算法 - labuladong的算法小抄

代码

class Solution {
    static final int[] MAP = new int[128]; // 映射
    static final int L = 10, R = 4; // 子串长度(哈希数的位数)与哈希数的进制
    static final int RL = (int) Math.pow(R, L - 1); // R^(L-1)

    // 把ACGT映射为0123
    static {
        MAP['A'] = 0;
        MAP['C'] = 1;
        MAP['G'] = 2;
        MAP['T'] = 3;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        Set<Integer> seen = new HashSet<>(); // 记录重复出现的哈希值
        Set<String> ans = new HashSet<>(); // 记录重复出现的字符串结果
        int n = s.length();
        // 把字符串转为四进制的数字数组
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = MAP[s.charAt(i)];
        int windowHash = 0; // 窗口子串的哈希值
        // 滑动窗口
        int left = 0, right = 0;
        while (right < n) {
            // 扩大窗口 -> 从右边移入字符 -> 在低位增加数字
            windowHash = windowHash * R + nums[right++];
            if (right - left == L) {
                // 根据哈希值判断是否见过相同的子串 如果出现过就把子串截取出来加入到答案数组中
                if (seen.contains(windowHash)) ans.add(s.substring(left, right));
                else seen.add(windowHash); // 之前没见过现在见过了吧
                // 缩小窗口 -> 从左边移出字符 -> 在高位删除数字
                windowHash = windowHash - nums[left++] * RL;
            }
        }
        return new ArrayList<>(ans);
    }
}

哈希数最大也就才 $4^{10}=1048576$，直接上长度为 $4^{10}+1$ 的数组计数，よゆう、よゆう～

class Solution {
    static final int[] HASH = new int[128];
    static final int L = 10, R = 4;
    static final int RL = (int) Math.pow(R, L - 1);
    static final int HASH_LEN = (int) Math.pow(R, L) + 1;

    static {
        HASH['A'] = 0;
        HASH['C'] = 1;
        HASH['G'] = 2;
        HASH['T'] = 3;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        int[] nums = new int[n]; 
        for (int i = 0; i < n; ++i) nums[i] = HASH[s.charAt(i)];
        int windowHash = 0;
        int left = 0, right = 0;
        int[] cnts = new int[HASH_LEN];
        List<String> ans = new ArrayList<>();
        while (right < n) {
            windowHash = windowHash * R + nums[right++];
            if (right - left == L) {
                if (++cnts[windowHash] == 2) ans.add(s.substring(left, right));
                windowHash = windowHash - nums[left++] * RL;
            }
        }
        return ans;
    }
}