資料結構
網路
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 次瀏覽
廣告