मान लीजिए हमारे पास एक DNA अनुक्रम है। जैसा कि हम जानते हैं, सभी DNA न्यूक्लियोटाइड्स की एक श्रृंखला से बने होते हैं जिन्हें A, C, G, और T जैसे संक्षिप्त किया जाता है, उदाहरण: "ACGAATTCCG"। DNA का अध्ययन करते समय, DNA के भीतर दोहराए गए अनुक्रमों की पहचान करना कभी-कभी उपयोगी होता है।
हमें एक विधि लिखनी है जो DNA अणु में एक से अधिक बार आने वाले सभी 10-अक्षर लंबे अनुक्रमों (उपस्ट्रिंग्स) को ढूंढे।
उदाहरण के लिए, यदि इनपुट "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" है, तो आउटपुट ["AAAAACCCCC", "CCCCCAAAAA"] होगा।
हल करने के चरण
ret नामक एक सरणी परिभाषित करें, n := s का आकार, visited और visited2 नामक दो सेट बनाएं
bitVal नामक एक मैप परिभाषित करें
ACGT के लिए संबंधित मान 0,1,2,3 bitVal में स्टोर करें
mask := 0
i को 0 से n-1 तक लूप करें
mask := mask * 4
mask := mask OR bitVal[s[i]]
mask := mask AND 0xFFFFF
यदि i < 9, तो अगले इटरेशन पर जाएं
इंडेक्स i-9 से 10 लंबाई का उपस्ट्रिंग ret में डालें
mask को visited2 में डालें
mask को visited में डालें
ret वापस करें
उदाहरण (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, ]
