ধরুন আমাদের একটি ডিএনএ সিকোয়েন্স আছে। আমরা জানি, সমস্ত DNA সংক্ষেপে A, C, G, এবং T-এর মতো নিউক্লিওটাইডের একটি সিরিজ দিয়ে গঠিত, উদাহরণস্বরূপ:"ACGAATTCCG"। যখন আমরা ডিএনএ অধ্যয়ন করি, তখন কখনও কখনও ডিএনএ-র মধ্যে পুনরাবৃত্তি ক্রমগুলি সনাক্ত করা কার্যকর হয়৷
ডিএনএ অণুতে একাধিকবার ঘটে এমন সমস্ত 10-অক্ষর-দীর্ঘ সিকোয়েন্স (সাবস্ট্রিং) খুঁজে পেতে আমাদের একটি পদ্ধতি লিখতে হবে।
তাই ইনপুট যদি হয় “AAAAACCCCCAAACCCCCCAAAAAAGGGTTT”, তাহলে আউটপুট হবে ["AAAAACCCCC", "CCCCCAAAAA"]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে ret সংজ্ঞায়িত করুন, n :=s এর আকার, ভিজিটেড এবং ভিজিটেড2 নামে দুটি সেট তৈরি করুন
-
বিটভাল নামে একটি মানচিত্র সংজ্ঞায়িত করুন।
-
ACGT-এর জন্য 0123-এর মতো সংশ্লিষ্ট মানগুলি butVal-এ সঞ্চয় করুন।
-
মুখোশ :=0
-
0 থেকে n – 1
রেঞ্জের i জন্য-
মুখোশ :=মাস্ক * 4
-
মুখোশ :=মাস্ট বা বিটভাল[s[i]]
-
মুখোশ :=মাস্ক এবং FFFFF
-
যদি আমি <9, তাহলে শুধু পরবর্তী পুনরাবৃত্তি চালিয়ে যান
-
সাবস্ট্রিং ফর্ম ইনডেক্স i – 9 থেকে 9, 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, ]
