【LeetCode每日一题】187. 重复的DNA序列 【哈希表+滑动窗口+字符串+位运算】
所有 DNA 都由一系列缩写为 'A','C','G' 和 'T' 的核苷酸组成,例如:"ACGAATTCCG"。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串,目标子串的长度为 10,且在 DNA 字符串 s 中出现次数超过一次。
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出:["AAAAACCCCC","CCCCCAAAAA"] 示例 2:
输入:s = "AAAAAAAAAAAAA" 输出:["AAAAAAAAAA"]
提示:
0 <= s.length <= 105 s[i] 为 'A'、'C'、'G' 或 'T'
题解: 最容易想到的方法就是遍历字符串,枚举所有的长度为10的子串,将其放入哈希表进行计数。
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.size();
map<string, int> m;
vector<string> ans;
for(int i = 0; i + 10 <= n; i++){
string now = s.substr(i, 10);
if(m[now] == 0){
m[now] = 1;
}
else{
if(m[now] == 1) ans.push_back(now), m[now] = 2;
}
}
return ans;
}
};
进阶题解:
class Solution {
const int L = 10;
unordered_map<char, int> bin = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> ans;
int n = s.length();
if (n <= L) {
return ans;
}
int x = 0;
for (int i = 0; i < L - 1; ++i) {
x = (x << 2) | bin[s[i]];
}
unordered_map<int, int> cnt;
for (int i = 0; i <= n - L; ++i) {
x = ((x << 2) | bin[s[i + L - 1]]) & ((1 << (L * 2)) - 1);
if (++cnt[x] == 2) {
ans.push_back(s.substr(i, L));
}
}
return ans;
}
};
复杂度分析
时间复杂度:O(N),其中 NN 是字符串 s 的长度。
空间复杂度:O(N)。