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