Medium

题目描述

DNA序列由一系列核苷酸组成，缩写为’A’、‘C’、‘G’和’T’。

例如，“ACGAATTCCG"是一个DNA序列。

在研究DNA时，识别DNA中的重复序列是很有用的。

给定一个表示DNA序列的字符串s，返回所有在DNA分子中出现超过一次的10个字母长的序列（子字符串）。你可以按任意顺序返回答案。

示例 1:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出: ["AAAAACCCCC","CCCCCAAAAA"]

示例 2:

输入: s = "AAAAAAAAAAAAA"
输出: ["AAAAAAAAAA"]

提示:

  • 1 <= s.length <= 10^5
  • s[i] 是 ‘A’、‘C’、‘G’ 或 ‘T’ 中的一个

解题思路

这道题要求找出DNA序列中所有重复出现的长度为10的子串。

方法一：滑动窗口 + 哈希表 最直观的方法是使用滑动窗口遍历所有长度为10的子串，用哈希表记录每个子串的出现次数。时间复杂度O(n)，空间复杂度O(n)。

方法二：位操作优化（推荐） 由于DNA只有4种字符，我们可以用2位二进制表示一个字符（A=0, C=1, G=2, T=3）。这样一个长度为10的子串可以用20位整数表示，大大节省空间。

具体实现：

  1. 将字符映射为数字：A→0, C→1, G→2, T→3
  2. 使用滑动窗口，每次移动时去掉最高位，加入新的最低位
  3. 用哈希集合记录见过的序列和重复的序列

这种方法的优势是空间效率更高，且比较操作更快。

方法三：Rolling Hash 使用多项式滚动哈希，可以在O(1)时间内计算新窗口的哈希值，但需要处理哈希冲突问题。

代码实现

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        if (s.length() <= 10) return {};
        
        unordered_map<char, int> mapping = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        unordered_set<int> seen;
        unordered_set<int> repeated;
        vector<string> result;
        
        int hash = 0;
        for (int i = 0; i < 10; i++) {
            hash = hash * 4 + mapping[s[i]];
        }
        seen.insert(hash);
        
        for (int i = 10; i < s.length(); i++) {
            hash = hash * 4 + mapping[s[i]];
            hash &= (1 << 20) - 1; // 保持20位
            
            if (seen.count(hash) && !repeated.count(hash)) {
                repeated.insert(hash);
                result.push_back(s.substr(i - 9, 10));
            }
            seen.insert(hash);
        }
        
        return result;
    }
};

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        if len(s) <= 10:
            return []
        
        mapping = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        seen = set()
        repeated = set()
        result = []
        
        # 计算第一个窗口的哈希值
        hash_val = 0
        for i in range(10):
            hash_val = hash_val * 4 + mapping[s[i]]
        seen.add(hash_val)
        
        # 滑动窗口
        for i in range(10, len(s)):
            hash_val = hash_val * 4 + mapping[s[i]]
            hash_val &= (1 << 20) - 1  # 保持20位
            
            if hash_val in seen and hash_val not in repeated:
                repeated.add(hash_val)
                result.append(s[i-9:i+1])
            seen.add(hash_val)
        
        return result

public class Solution {
    public IList<string> FindRepeatedDnaSequences(string s) {
        if (s.Length <= 10) return new List<string>();
        
        var mapping = new Dictionary<char, int> {
            {'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}
        };
        var seen = new HashSet<int>();
        var repeated = new HashSet<int>();
        var result = new List<string>();
        
        int hash = 0;
        for (int i = 0; i < 10; i++) {
            hash = hash * 4 + mapping[s[i]];
        }
        seen.Add(hash);
        
        for (int i = 10; i < s.Length; i++) {
            hash = hash * 4 + mapping[s[i]];
            hash &= (1 << 20) - 1; // 保持20位
            
            if (seen.Contains(hash) && !repeated.Contains(hash)) {
                repeated.Add(hash);
                result.Add(s.Substring(i - 9, 10));
            }
            seen.Add(hash);
        }
        
        return result;
    }
}

var findRepeatedDnaSequences = function(s) {
    if (s.length <= 10) return [];
    
    const mapping = new Map([['A', 0], ['C', 1], ['G', 2], ['T', 3]]);
    const seen = new Set();
    const repeated = new Set();
    const result = [];
    
    let hash = 0;
    for (let i = 0; i < 10; i++) {
        hash = hash * 4 + mapping.get(s[i]);
    }
    seen.add(hash);
    
    for (let i = 10; i < s.length; i++) {
        hash = hash * 4 + mapping.get(s[i]);
        hash &= (1 << 20) - 1; // 保持20位
        
        if (seen.has(hash) && !repeated.has(hash)) {
            repeated.add(hash);
            result.push(s.substring(i - 9, i + 1));
        }
        seen.add(hash);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串 s 的长度。使用位操作优化后，每个子串只需要一个整数存储，相比直接存储字符串更节省空间。