Repeated DNA Sequences

原題鏈接Repeated DNA Sequences

在給定字符串中尋找重復出現的序列，每個序列長度為10

可以采用unordered_map記錄每個序列出現的個數，將出現超過一次的添加到結果集中

代碼如下

class Solution { public:vector<string> findRepeatedDnaSequences(string s) {if(s.size() < 10) return {};vector<string> res;unordered_map<string, int> hash;size_t first = 0;size_t last = 10;while(last <= s.size()){auto str = s.substr(first, last - first);if(hash[str] == 1)res.emplace_back(str);++hash[str];++first;++last;}return res;} };

但是這種方法每次都需要調用substr獲取子串，容易造成性能瓶頸，有什么方法不用調用substr也能判斷當前的這個子串出現過呢

由于規定了子串長度為10，而且子串中只能出現”AGCT“四個字符中的一個，那么可以考慮用20個bit來表示長度為10的子串，其中每個字符占兩bit。隨后采用滑動窗口的思想，新到的字符添加到20bit的低位，溢出的字符丟掉

代碼如下

class Solution { public:vector<string> findRepeatedDnaSequences(string s) {if(s.size() < 10) return {};vector<string> res;unordered_map<int, int> hash;int val = 0;/* 掩碼，用于將左溢出的兩位清零 */int mask = (1 << 20) - 1;/* 每個字符占兩位，toBit要保證能區分開四個字符 */for(int i = 0; i < 10; ++i)val = (val << 2) | toBit(s[i]);hash[val] = 1;for(int i = 10; i < s.size(); ++i){val = ((val << 2) | toBit(s[i])) & mask;if(hash[val] == 1)res.emplace_back(s.substr(i - 10 + 1, 10));++hash[val];}return res;} private:int toBit(char ch){switch(ch){case 'A':return 0;case 'G':return 1;case 'C':return 2;case 'T':return 3;}} };

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----寻找给定字符串中重复出现的子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。