Hoán vị trong chuỗi trong C ++

Giả sử chúng ta có hai chuỗi s1 và s2, chúng ta phải viết một hàm để trả về true nếu s2 chứa hoán vị của s1. Vì vậy, chúng ta có thể nói rằng một trong những hoán vị của chuỗi đầu tiên là chuỗi con của chuỗi thứ hai. Vì vậy, nếu chuỗi s1 =“abc” và chuỗi thứ hai s2 là “findcab”, thì kết quả sẽ là true, vì hoán vị của “abc” là true. Đó là "taxi".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo hai vectơ cnt1 và cnt2 có kích thước 26
• cho tôi trong phạm vi từ 0 đến s1
  • tăng giá trị của cnt1 [s1 [i] - ‘a’] lên 1
• j:=0 và bắt buộc:=kích thước của s1
• cho tôi trong phạm vi từ 0 đến kích thước của s2
  • x:=s2 [i]
  • tăng cnt2 [x - ‘a’] lên 1
  • nếu cnt1 [x - ‘a’] và cnt2 [x - ‘a’] <=cnt [x - ‘a’], thì
    • giảm theo yêu cầu 1
  • while j <=i và cnt2 [s2 [j] - ‘a’] - 1> =cnt1 [s2 [j] - ‘a’], thực hiện
    • giảm cnt2 [s2 [j] - ‘a’] đi 1
    • tăng j lên 1
  • nếu i - j + 1 =kích thước của s1 và bắt buộc =0, thì trả về true
• trả về false.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool checkInclusion(string s1, string s2) {
      vector <int> cnt1(26), cnt2(26);
      for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++;
      int j = 0;
      int required = s1.size();
      for(int i = 0; i < s2.size(); i++){
         char x = s2[i];
         cnt2[x - 'a']++;
         if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--;
         while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){
            cnt2[s2[j] - 'a']--;
            j++;
         }
         if(i - j + 1 == s1.size() && required == 0){
            return true;
         }
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.checkInclusion("abc", "findcab"));
}

Đầu vào

"abc"
"findcab"

Đầu ra

1