题目的主要信息:

  • 一串只由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;
    }
};

复杂度分析:

  • 时间复杂度:O(n2)O(n^2),外循环遍历一次数组,内循环find函数的复杂度为O(10n)O(10n),map的插入为O(log2n)O(log_2n),因此总复杂度为O(n2)O(n^2)
  • 空间复杂度:O(n)O(n),map最大的空间为不同子串的个数,最坏情况下都不同

方法二:哈希表

具体做法:

上述使用find函数的查找太耗费时间了,我们可以使用哈希表直接去重计数,只需要将unordered_map的key值设置为字符串子串,value值设置为出现次数,第一次遍历所有的子串统计出现次数。第二次还是遍历所有的子串,不能直接遍历哈希表,因为哈希表中位置是不一定的,输出需要按照子串第一次出现的位置来,因此还是遍历原串的所有子串,查询其在哈希表中的次数,如果次数大于1,记录输出,同时从哈希表中将其删除,避免后续再次遇到了,重复输出。

alt

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;
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),单独遍历两次字符串,哈希表的操作都是O(1)O(1)
  • 空间复杂度:O(n)O(n),哈希表的大小最坏情况下为n10n-10