数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时装研究
法律研究C++ 中的字符串排列
假设我们有两个字符串 s1 和 s2，我们必须编写一个函数，如果 s2 包含 s1 的排列，则返回 true。所以我们可以说第一个字符串的一个排列是第二个字符串的子字符串。因此，如果字符串 s1 =“abc”，第二个字符串 s2 为“findcab”，则结果将为 true，因为“abc”的排列为 true。即“cab”。
要解决这个问题，我们将遵循以下步骤 -
- 创建大小为 26 的两个向量 cnt1 和 cnt2
- 对于范围 0 到 s1 中的 i
- 将 cnt1[s1[i] - 'a'] 的值增加 1
- j := 0 并且 required := s1 的大小
- 对于范围 0 到 s2 的大小中的 i
- 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
- 返回 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
更新日期：2020-04-29
581 次浏览
广告