Tìm tất cả các đảo ngữ trong một chuỗi trong C ++

Giả sử chúng ta có một chuỗi s và một chuỗi không rỗng p, chúng ta phải tìm tất cả các chỉ số bắt đầu của các phép đảo chữ của p trong s. Các chuỗi chỉ bao gồm các chữ cái thường và độ dài của cả hai chuỗi s và p sẽ không lớn hơn 20 và 100. Vì vậy, ví dụ:nếu s:"cbaebabacd" p:"abc", thì đầu ra sẽ là [0, 6 ], ở chỉ mục 0, nó là “cba” và một chỉ số khác là “bac”, đây là những từ đảo ngữ của “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

• cho bên phải:=0 đến 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 bên 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

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;
}
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("cbaebabacd", "abc")) ;
}

Đầu vào

"cbaebabacd"
"abc"

Đầu ra

[0, 6, ]