题目描述
DNA序列 由一系列核苷酸组成,缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
例如,”ACGAATTCCG” 是一个 DNA序列 。
在研究 DNA 时,识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
样例
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC","CCCCCAAAAA"]
示例 2:
输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]
数据结构(hash表)
C++ 代码
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<string, int> hash;
vector<string> res;
for (int i = 9; i < s.size(); i ++)
{
string str = s.substr(i - 9, 10);
hash[s.substr(i - 9, 10)] ++;
if (hash[str] == 2) res.push_back(str);
}
return res;
}
};