題目
給定兩個字串 s1 和 s2，寫一個函式來判斷 s2 是否包含 s1 的排列，換句話說，第一個字串的排列之一是第二個字串的子串，
示例1:
輸入: s1 = "ab" s2 = "eidbaooo" 輸出: True 解釋: s2 包含 s1 的排列之一 ("ba").
示例2:
輸入: s1= "ab" s2 = "eidboaoo" 輸出: False
解題思路
滑動視窗+哈希
用一個26長度的陣列記錄字串s1的哈希值，維護一個s1長度的滑動視窗，滑動視窗長度固定不變,每次向右移動一個單位，記錄當前滑動視窗區間的哈希值，再與維護字串s1的哈希值的陣列比較，
AC代碼
時間復雜度:O(n+m*n)
class Solution {
public:
int num[26];//維護字串s1的哈希值
int ans[26];//維護滑動視窗的哈希值
bool checkInclusion(string s1, string s2) {
int n=s1.size();
for(int i=0;i<n;i++){
num[s1[i]-'a']++;
}
int l=0,r=n-1;
while(r<s2.size()){
//記錄當前滑動視窗的哈希值
for(int i=l;i<=r;i++){
ans[s2[i]-'a']++;
}
int flag=1;
for(int i=0;i<n;i++){
if(ans[s1[i]-'a']!=num[s1[i]-'a']){
flag=0;
break;
}
}
//如果兩陣列哈希值相等，回傳結果
if(flag){
return true;
}
//將記錄當前滑動視窗的陣列值清為0
for(int i=l;i<=r;i++){
ans[s2[i]-'a']=0;
}
//滑動視窗右移
l++;
r++;
}
return false;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258775.html
標籤：其他