首页 > 代码库 > [LeetCode]Repeated DNA Sequences

[LeetCode]Repeated DNA Sequences

题目:Repeated DNA Sequences

给定包含A、C、G、T四个字符的字符串找出其中十个字符的重复子串。

思路:

首先,string中只有ACGT四个字符,因此可以将string看成是1,3,7,20这三个数字的组合串;

并且可以发现{ACGT}%5={1,3,2,0};于是可以用两个位就能表示上面的四个字符;

同时,一个子序列有10个字符,一共需要20bit,即int型数据类型就能表示一个子序列;

这样可以使用计数排序的思想来统计重复子序列;

这个思路时间复杂度只有O(n),但是空间复杂度2^20byte辅助空间;

vector<string> LeetCode::findRepeatedDnaSequences(string s){
    vector<string> ret;
    if (s.size() < 11)return ret;
    char count[1048576] = {0};//0x000fffff = 1048575
    int index = 0;
    for (size_t i = 0; i < 9; ++i){//先求第一个子序列
        int value = http://www.mamicode.com/s[i] - A + 1;//char转成int
        value %= 5;//对5求余,转成2bit的大小
        index = index << 2 | value;//合并成一个值
    }
    for (size_t i = 9; i < s.size(); ++i){
        int value = http://www.mamicode.com/s[i] - A + 1;//char转成int
        value %= 5;//对5求余,转成2bit的大小
        index = index << 2 | value;//合并成一个值
        index = index & 0x000fffff;//清除前面移位的高位无效数字
        ++count[index];
        if (count[index] < 0)count[index] = 3;
        if (count[index] == 2){//防止重复加入
            ret.push_back(s.substr(i - 9, 10));
        }
    }
    return ret;
}

 

[LeetCode]Repeated DNA Sequences