Giả sử chúng ta có một chuỗi DNA. Như chúng ta đã biết, tất cả DNA đều được cấu tạo từ một chuỗi nucleotide viết tắt như A, C, G, T, ví dụ:"ACGAATTCCG". Khi chúng ta đang nghiên cứu về DNA, đôi khi việc xác định các trình tự lặp lại trong DNA sẽ rất hữu ích.
Chúng ta phải viết một phương pháp để tìm tất cả các trình tự (chuỗi con) dài 10 ký tự xuất hiện nhiều lần trong một phân tử DNA.
Vì vậy, nếu đầu vào là “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”, thì đầu ra sẽ là ["AAAAACCCCC", "CCCCCAAAAA"].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một mảng ret, n:=kích thước của s, tạo hai tập hợp được gọi là đã thăm và đã thăm2
-
xác định một bản đồ được gọi là bitVal.
-
Lưu trữ các giá trị tương ứng cho ACGT như 0123 vào butVal.
-
mặt nạ:=0
-
cho tôi trong phạm vi từ 0 đến n - 1
-
mask:=mask * 4
-
mask:=mast OR bitVal [s [i]]
-
mask:=mask AND FFFFF
-
nếu tôi <9, thì chỉ cần tiếp tục với lần lặp tiếp theo
-
chèn chỉ mục biểu mẫu chuỗi con i - 9 đến 9, vào ret
-
chèn dấu vào đã thăm2.
-
-
chèn mặt nạ vào đã truy cập
-
-
trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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"));
} Đầu vào
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Đầu ra
[AAAAACCCCC, CCCCCAAAAA, ]