Leetcode 187 Repeated DNA Sequences

triplebee

发布于 2018-01-12 14:49:05

6520

发布于 2018-01-12 14:49:05

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

十个字符表示一个DNA序列，找出多次出现的序列。

移动头尾两个指针，用map存储已经探测过的序列，当该序列之前出现过一次的时候，则将它加入答案中。

在由前一个位置的序列得到下一个位置的序列时可以采用位运算的方式。

对AGCT四个字母编码，0，1，2，3，则两个bit可以表示一个字母，十个字符正好20bit，可以用int类型表示。

移动到下一位时用上一个位置的int值向高位移动2bit，然后或上新的2bit，在与0xfffff求与保留低20位。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if(s.size() < 10) return res;
        unordered_map<int, int> mp;
        unordered_map<char, int> id;
        id['A'] = 0;
        id['C'] = 1;
        id['G'] = 2;
        id['T'] = 3;
        int temp = 0;
        for(int i = 0; i < s.size(); i++)
        {
            temp = (temp<<2| (id[s[i]] & 3)) & 0xfffff;
            if(i > 8)
            {
                if(mp[temp] == 1) res.push_back(s.substr(i - 9,10));
                mp[temp]++;
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-02-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除

bit