LeetCode 187. 重复的DNA序列

Categories:

题目描述
思路分析
1. 解法一：位编码 + 哈希（推荐）
相似题目

题目描述

✅ 187. 重复的DNA序列

思路分析

解法一：位编码 + 哈希（推荐）

核心思路：

DNA 字符只包含 4 种，可用 2 bit 编码。

滑动窗口维护长度为 10 的编码值，滚动更新。

用集合记录出现过的编码，重复出现则加入结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，哈希集合存储编码值。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        if (s.length() < 10) {
            return res;
        }

        Map<Character, Integer> map = new HashMap<>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);

        int mask = (1 << 20) - 1;
        int hash = 0;
        Set<Integer> seen = new HashSet<>();
        Set<Integer> added = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            hash = ((hash << 2) | map.get(s.charAt(i))) & mask;

            if (i >= 9) {
                if (seen.contains(hash) && !added.contains(hash)) {
                    res.add(s.substring(i - 9, i + 1));
                    added.add(hash);
                }
                seen.add(hash);
            }
        }

        return res;
    }
}

func findRepeatedDnaSequences(s string) []string {
	res := make([]string, 0)
	if len(s) < 10 {
		return res
	}

	val := map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
	mask := (1 << 20) - 1
	hash := 0
	seen := make(map[int]bool)
	added := make(map[int]bool)

	for i := 0; i < len(s); i++ {
		hash = ((hash << 2) | val[s[i]]) & mask
		if i >= 9 {
			if seen[hash] && !added[hash] {
				res = append(res, s[i-9:i+1])
				added[hash] = true
			}
			seen[hash] = true
		}
	}

	return res
}

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	字符串匹配
1392. 最长快乐前缀	困难	哈希
187. 重复的DNA序列	中等	滚动哈希
1044. 最长重复子串	困难	哈希
686. 重复叠加字符串匹配	中等	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/56017792