C++ 字符串的排列
c++server side programmingprogramming
假设我们有两个字符串 s1 和 s2，我们需要编写一个函数，如果 s2 包含 s1 的排列，则返回 true。这样，我们就可以说第一个字符串的排列之一是第二个字符串的子字符串。因此，如果字符串 s1 = "abc"，而第二个字符串 s2 为 "findcab"，则结果为 true，因为 "abc" 的排列为真。这就是"cab"。
为了解决这个问题，我们将遵循以下步骤 −
- 创建两个大小为 26 的向量 cnt1 和 cnt2
- i 的值范围从 0 到 s1
- 将 cnt1[s1[i] – ‘a’] 的值增加 1
- j := 0 且 required := s1 的大小
- i 的值范围从 0 到 s2 的大小
- x := s2[i]
- 将 cnt2[x – ‘a’] 的值增加 1
- 如果 cnt1[x – ‘a’] 且 cnt2[x – ‘a’] <= cnt[x – ‘a’]，则
- 将 required 减 1
- 当 j <= i 且 cnt2[s2[j] – ‘a’] – 1 >= cnt1[s2[j] – ‘a’] 时，执行
- 将 cnt2[s2[j] – ‘a’] 减 1
- 将 j 加 1
- 如果 i – j + 1 = s1 的大小且 required = 0，则返回 true
- return 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
