标签: 位运算 哈希表 字符串 滑动窗口 哈希函数 滚动哈希
难度: Medium
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 <= 105s[i]=='A'、'C'、'G' or 'T'运行时间: 38 ms
内存: 26.8 MB
from collections import defaultdict
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
n = len(s)
if n < 10:
return []
counter = defaultdict(int)
mapping = {'A':0, 'C':1, 'G':2, 'T':3}
res = []
curr = 0
for i in range(9):
curr = (curr << 2) | mapping[s[i]]
for i in range(9, n):
curr = ((curr << 2) | mapping[s[i]]) & ((1 << 20) - 1)
counter[curr] += 1
if counter[curr] == 2:
res.append(s[(i - 9):(i + 1)])
return res
该题解采用滑动窗口和位操作的方法来寻找重复的DNA序列。首先，将四个可能的字符（'A', 'C', 'G', 'T'）映射到2位的整数（分别是0, 1, 2, 3），以便使用位操作来更新当前窗口的哈希值。使用一个长度为10的滑动窗口，遍历字符串，每向右移动窗口一位，就更新当前窗口表示的数字（通过左移两位并添加新字符的映射值，同时确保数字长度不超过20位，即10个字符的长度）。每个窗口的数字作为哈希表的键，记录每个序列出现的次数。当某个序列第二次出现时，将其添加到结果列表中。这种方法避免了直接使用字符串子串比较，而是通过计算较小的整数值来优化比较过程。
时间复杂度: O(n)
空间复杂度: O(n)
from collections import defaultdict
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
n = len(s)
if n < 10:
return [] # 如果长度小于10，直接返回空列表
counter = defaultdict(int) # 用来计数每个序列出现的次数
mapping = {'A':0, 'C':1, 'G':2, 'T':3} # 字符到数字的映射
res = [] # 用来存储结果的列表
curr = 0 # 当前窗口对应的数字
for i in range(9):
curr = (curr << 2) | mapping[s[i]] # 初始化当前数字，对前9个字符进行编码
for i in range(9, n):
curr = ((curr << 2) | mapping[s[i]]) & ((1 << 20) - 1) # 更新当前数字，并保持长度为20位
counter[curr] += 1 # 增加当前序列的计数
if counter[curr] == 2: # 如果某个序列出现了第二次
res.append(s[(i - 9):(i + 1)]) # 将其添加到结果列表
return res # 返回结果列表
选择长度为10的窗口来寻找重复的DNA序列主要是因为这个长度在生物学研究中具有特定的实用意义，同时也是一个在计算上可行的长度。在生物学中，长度为10的DNA序列足够显示遗传信息的重复模式，这对于识别基因的某些特性和功能非常重要。此外，在算法设计上，长度为10使得通过位操作处理DNA序列变得高效，因为整个序列可以压缩到一个20位的整数内，这样可以使用标准的数据类型（如整型）进行快速处理，而不需要使用更复杂的数据结构。
在位操作中，以确保数字长度不超过20位，使用的关键技术是位掩码。在更新当前窗口表示的数字时，首先通过将当前值左移两位来为新字符留出空间，然后通过位或操作（|）添加新字符的映射值。为了确保这个数字不超过20位，使用一个位掩码将数字的长度限制在20位。具体操作为对数字进行与操作（&）与掩码 `((1 << 20) - 1)`。这个掩码是一个20位全为1的二进制数，这样可以确保在添加新字符后，数字的最高位（超出20位的部分）被清零，从而保持数字总是在20位以内。
选择将'A', 'C', 'G', 'T'映射到2位的整数是因为这四个字符是DNA序列的全部可能字符，而2位二进制数正好可以表示4种不同的状态（00, 01, 10, 11）。这样的映射是最为紧凑和高效的方式，因为它刚好利用了2位二进制数的全部编码能力，没有浪费。如果使用更多位数进行映射，如3位或4位，将会产生额外的未使用状态，这不仅增加了处理的复杂性，还可能导致存储效率的下降。因此，使用2位整数进行映射是一种既简洁又高效的方法。