题目的主要信息:
- 一串只由ATCG字母组成的字符串,求其中出现次数超过1的长度为10的片段
- 输出顺序需要按照在原始字符串中第一次的出现顺序
方法一:暴力查找
具体做法:
字符串的find函数,查找出子串在原串中是否出现,如果查找到了返回的就是该子串第一次出现的位置。因此我们可以遍历字符串所有长度为10的子串,然后在原串中查找它出现的位置,如果它出现的位置不是现有子串的位置,说明前面出现过了,这个子串就是出现次数超过1的,我们可以记录输出它。
但是,又要面临一个去重和输出顺序的问题,因此可以使用容器map,key值记录第一次出现的下标,map就会按照下标排序,同时如果相同下标出现还会自动去重,value值则记录相应的字符子串。统计完成后,遍历map即可得到输出序列。
class Solution {
public:
vector<string> repeatedDNA(string DNA) {
vector<string> res;
map<int, string> mp; //记录重复片段第一次出现的位置和片段
for(int i = 0; i <= DNA.size() - 10; i++){ //遍历所有长度为10的片段
string s = DNA.substr(i, 10);
int pos = DNA.find(s); //查找该片段第一次出现的位置
if(pos != i) //如果该片段第一次出现是在此处,说明前面出现过了
mp.insert({pos, s}); //将前面第一次出现的位置和片段插入map
}
for(auto iter = mp.begin(); iter != mp.end(); iter++) //map会对位置排序,遍历将片段取出即可
res.push_back(iter->second);
return res;
}
};
复杂度分析:
- 时间复杂度:,外循环遍历一次数组,内循环find函数的复杂度为,map的插入为,因此总复杂度为
- 空间复杂度:,map最大的空间为不同子串的个数,最坏情况下都不同
方法二:哈希表
具体做法:
上述使用find函数的查找太耗费时间了,我们可以使用哈希表直接去重计数,只需要将unordered_map的key值设置为字符串子串,value值设置为出现次数,第一次遍历所有的子串统计出现次数。第二次还是遍历所有的子串,不能直接遍历哈希表,因为哈希表中位置是不一定的,输出需要按照子串第一次出现的位置来,因此还是遍历原串的所有子串,查询其在哈希表中的次数,如果次数大于1,记录输出,同时从哈希表中将其删除,避免后续再次遇到了,重复输出。
class Solution {
public:
vector<string> repeatedDNA(string DNA) {
vector<string> res;
unordered_map<string, int> mp; //使用哈希表统计长度为10的片段出现次数
for(int i = 0; i <= DNA.size() - 10; i++){ //遍历每个长度为10的片段
string s = DNA.substr(i, 10);
mp[s]++; //统计次数
}
for(int i = 0; i <= DNA.size() - 10; i++){ //再次遍历每个长度为10的片段,因为输出要按照位置
string s = DNA.substr(i, 10);
if(mp[s] > 1){ //遇到出现次数大于1的片段,将其加入输出
res.push_back(s);
mp.erase(s); //删去,防止后续再次加入
}
}
return res;
}
};
复杂度分析:
- 时间复杂度:,单独遍历两次字符串,哈希表的操作都是
- 空间复杂度:,哈希表的大小最坏情况下为