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