Giả sử chúng ta có hai chuỗi S và T, chúng ta phải tìm tất cả các chỉ số bắt đầu của các từ đảo ngữ của S trong T. Các chuỗi chỉ bao gồm các chữ cái viết thường và độ dài của cả hai chuỗi S và T sẽ không lớn hơn 20 và 100.
Vì vậy, nếu đầu vào là S ="cab" T ="bcabxabc", thì đầu ra sẽ là [0, 1, 5,], là các chuỗi con "bca", "cab" và "abc".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
Xác định bản đồ m, n:=kích thước của s, đặt bên trái:=0, bên phải:=0, bộ đếm:=kích thước của p
-
xác định ans mảng
-
lưu trữ tần số của các ký tự trong p vào bản đồ m
-
bên phải:=0 to n - 1
-
nếu m có s [phải] và m [s [phải]] khác 0, thì giảm m [s [phải]] đi 1, giảm bộ đếm đi 1 và nếu bộ đếm =0, sau đó chèn trái vào ans
-
nếu không thì
-
trong khi trái
-
nếu s [left] không có trong m, thì hãy tăng bộ đếm lên 1 và tăng m [s [left]] lên 1
-
tăng sang trái 1
-
nếu m có s [phải] và m [s [phải]] khác 0, thì giảm sang phải 1 và đi ra khỏi vòng lặp
-
-
nếu m không có s [left], thì đặt left:=right + 1
-
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
#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;
}
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
map <char, int> m;
int n = s.size();
int left = 0, right = 0;
int counter = p.size();
vector <int> ans;
for(int i = 0; i < p.size(); i++) m[p[i]]++;
for(int right = 0; right < n; right++){
if(m.find(s[right]) != m.end() && m[s[right]]){
m[s[right]]--;
counter--;
if(counter == 0)ans.push_back(left);
} else {
while(left<right){
if(m.find(s[left]) != m.end()) {
counter++;
m[s[left]]++;
}
left++;
if(m.find(s[right]) != m.end() && m[s[right]]){
right--;
break;
}
}
if(m.find(s[left])==m.end())left = right + 1;
}
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.findAnagrams("bcabxabc", "cab")) ;
} Đầu vào
"bcabxabc", "cab"
Đầu ra
[0, 1, 5, ]