मान लीजिए कि हमारे पास डीएनए अनुक्रम है। जैसा कि हम जानते हैं, सभी डीएनए ए, सी, जी, और टी जैसे संक्षिप्त न्यूक्लियोटाइड की एक श्रृंखला से बना है, उदाहरण के लिए:"एसीजीएएटीटीसीसीजी"। जब हम डीएनए का अध्ययन कर रहे होते हैं, तो कभी-कभी डीएनए के भीतर दोहराए गए अनुक्रमों की पहचान करना उपयोगी होता है।
डीएनए अणु में एक से अधिक बार आने वाले सभी 10-अक्षर-लंबे अनुक्रम (सबस्ट्रिंग) को खोजने के लिए हमें एक विधि लिखनी होगी।
इसलिए यदि इनपुट "AAAAACCCCCAAAAACCCCCAAAAAGGGTTT" जैसा है, तो आउटपुट ["AAAAACCCCCC", "CCCCCAAAAA"] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक सरणी रिट परिभाषित करें, n :=s का आकार, दो सेट बनाएं जिन्हें विज़िट किया गया और विज़िट किया गया2
कहा जाता है -
बिटवैल नामक मानचित्र को परिभाषित करें।
-
एसीजीटी के लिए 0123 जैसे संबंधित मानों को butVal में संग्रहित करें।
-
मुखौटा :=0
-
मैं के लिए 0 से n - 1 की सीमा में
-
मुखौटा:=मुखौटा * 4
-
मुखौटा:=मस्तूल या बिटवैल [s[i]]
-
मुखौटा:=मुखौटा और एफएफएफएफएफ
-
अगर मैं <9, तो बस अगले पुनरावृत्ति के लिए जारी रखें
-
सबस्ट्रिंग फॉर्म इंडेक्स i - 9 से 9, रिट में डालें
-
विज़िट किए गए2 में चिह्न डालें.
-
-
विज़िट किए गए में मास्क डालें
-
-
वापसी रिट
उदाहरण(C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
vector<string>findRepeatedDnaSequences(string s) {
vector <string> ret;
int n = s.size();
set <int> visited;
set <int> visited2;
map <char, int> bitVal;
bitVal['A'] = 0;
bitVal['C'] = 1;
bitVal['G'] = 2;
bitVal['T'] = 3;
lli mask = 0;
for(int i = 0; i < n; i++){
mask <<= 2;
mask |= bitVal[s[i]];
mask &= 0xfffff;
if(i < 9) continue;
if(visited.count(mask) && !visited2.count(mask)){
ret.push_back(s.substr(i - 9, 10));
visited2.insert(mask);
}
visited.insert(mask);
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
} इनपुट
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
आउटपुट
[AAAAACCCCC, CCCCCAAAAA, ]