题目来源:
leetcode题目,网址:187. 重复的DNA序列 - 力扣(LeetCode)
解题思路:
使用两个哈希表,一个存放已遍历过的长度为 10 的字符串,另一个存放重复的长度为 10 的字符串。顺序遍历后将后者按要求输出即可。
解题代码:
class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {unordered_set<string> repeated;unordered_set<string> set;for(int i=0;i<(int)s.length()-9;i++){string temp=s.substr(i,10);if(set.count(temp)!=0){repeated.insert(temp);}else{set.insert(temp);}}vector<string> res;unordered_set<string>::iterator it;for(it=repeated.begin();it!=repeated.end();it++){res.push_back(*it);} return res;}
};
总结:
官方题解给出了两种解法。第一种是哈希表计数。第二种是哈希表+滑动窗口+位运算。