DNA序列 由一系列核苷酸组成,缩写为 'A'
, 'C'
, 'G'
和 'T'
.。
- 例如,
"ACGAATTCCG"
是一个 DNA序列 。
在研究 DNA 时,识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s
,返回所有在 DNA 分子中出现不止一次的 长度为 10
的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC","CCCCCAAAAA"]
示例 2:
输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
// 定义哈希映射,用于将字符转换为二进制
Map<Character, Integer> map = new HashMap<>();
map.put('A', 0);
map.put('C', 1);
map.put('G', 2);
map.put('T', 3);
// 存储子串出现次数的哈希表
Map<Integer, Integer> seqMap = new HashMap<>();
// 存储结果列表
List<String> res = new ArrayList<>();
// 遍历原始字符串
for (int i = 0; i <= s.length() - 10; i++) {
// 计算当前子序列的哈希值,采用 rolling hash 算法
int curSeq = 0;
for (int j = i; j < i + 10; j++) {
curSeq = (curSeq << 2) | map.get(s.charAt(j));
}
// 如果哈希表中已经存在该子串,则将其添加到结果列表中
if (seqMap.containsKey(curSeq) && seqMap.get(curSeq) == 1) {
res.add(s.substring(i, i + 10));
}
// 更新哈希表中该子串的出现次数
seqMap.put(curSeq, seqMap.getOrDefault(curSeq, 0) + 1);
}
return res;
}
}
标签:map,Karp,DNA,leetcode187,序列,字符串,put,new,Rabin
From: https://blog.51cto.com/u_12550160/6186008