2020-08-08

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA
中的重复序列有时会对研究非常有帮助。

编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出：[“AAAAACCCCC”,
“CCCCCAAAAA”]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-dna-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

每次截取长度为10的字符串，然后放入哈希表中，如果在哈希表中已经出现 则数量+1，第一次出现则为1。
然后遍历哈希表，如果哈希表中数量大于1，则将字符串放入数组中，最后返回数组。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {   
    vector<string>res;
    map<string,int>wordMap;
    string tmp="";//临时字符串
    for(int i=0;i<s.size();i++)
    {
        tmp=s.substr(i,10);//截10长度字符串
        if(wordMap.find(tmp)!=wordMap.end())//在哈希表中出现
        {
            wordMap[tmp]+=1;//数量再加1
        }else
        {
             wordMap[tmp]=1;//第一次出现则设置为1
        }            
    }
    for(auto i=wordMap.begin();i!=wordMap.end();i++)//遍历哈希表
    {
        if(i->second>1)//如果哈希表中出现数量大于1
        {
            res.push_back(i->first);//将该字符串放入数组中
        }
    }
    return res;
    }
};