Find Repeated DNA Sequences

发表于 | 分类于

Find Repeated DNA Sequences

题目描述：

定义长度为10的DNA片段，找到给定字符串中所有出现超过1次的DNA字符串片段。

例子：

具体描述可以看LeetCode187

解题思路：

我们用一个哈希表保存该字符串是否出现，用一个哈希表来表示是否已经保存到结果中即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size() <= 10) return res;
        set<string> hash;
        //保存该字符串是否已经出现
        set<string> table;
        //保存该字符串是否已经保存到结果res中
        for (int i = 0; i <= s.size() - 10; i++){
            if (hash.find(s.substr(i, 10)) == hash.end()){
                hash.insert(s.substr(i, 10));
            }else{
                if (table.find(s.substr(i, 10)) == table.end()){
                    table.insert(s.substr(i, 10));
                    res.push_back(s.substr(i, 10));
                }
            }
        }
        return res;
    }
};