C ++中的字符串排列

假设我们有两个字符串s1和s2，如果s2包含s1的排列，我们必须编写一个函数返回true。因此，可以说第一个字符串的排列之一是第二个字符串的子字符串。因此，如果字符串s1 =“ abc”，第二个字符串s2是“ findcab”，那么结果将为true，因为“ abc”的排列为true。那就是“小室”。

为了解决这个问题，我们将遵循以下步骤-

• 创建大小为26的两个向量cnt1和cnt2

• 对于i，范围为0至s1

• 将cnt1 [s1 [i] –'a']的值增加1

• j：= 0且必填：= s1的大小

• 对于范围从0到s2的i

• 将cnt2 [s2 [j] –'a']减少1

• 将j增加1

• 减少1

• x：= s2 [i]

• 将cnt2 [x –'a']增加1

• 如果cnt1 [x –'a']和cnt2 [x –'a'] <= cnt [x –'a']，则

• 当j <= i和cnt2 [s2 [j] –'a'] – 1> = cnt1 [s2 [j] –'a']时，

• 如果i – j + 1 = s1的大小且要求= 0，则返回true

• 返回false。

例子（C ++）

让我们看下面的实现以更好地理解-

#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"));
}

输入项

"abc"
"findcab"

输出结果

1