leetcode--187--重复的DNA序列

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

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

示例：

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

链接：https://leetcode-cn.com/problems/repeated-dna-sequences

思路：
1、遍历字符串，拿到所有长度为10的子串，将子串存于字典dt中，其中key为子串，value值为子串出现的次数
2、遍历字典，value值大于1的即为满足需要的子串

Python代码：

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        dt = {}

        i=0
        size = len(s)
        while i+9<=size:
            substr = s[i:i+10]
            if substr not in dt:
                dt[substr] = 1
            else:
                dt[substr] += 1
            i += 1
        
        ret = []
        for k in dt:
            if dt[k]>1:
                ret.append(k)
        return ret

C++代码：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        map<string, int> dt;
        int size = s.size();

        for(int i=0; i+9<=size; i++){
            string sub_str = s.substr(i,10);
            if (dt.find(sub_str)==dt.end()){
                dt[sub_str] = 1;
            }else{
                dt[sub_str] += 1;
            }
        }

        vector<string> ret;
        for (auto key:dt){
            if (key.second>1){
                ret.push_back(key.first);
            }
        }
        return ret;
    }
};