Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
给定两个字符串s1和s2，编写函数判定s2是否是s1的置换字符串。意即判定s1的某种排列是否出现在s2中。
Example 1:
Input:s1 ="ab" s2 ="eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1= "ab"s2 ="eidboaoo"
Output: False
Note:
- The input strings only contain lower case letters.
- The length of both given strings is in range [1, 10,000].
思路
- try find a window (i, j) where s2.substr(i, j + 1 - i) contains all chars in s1;
- once found, try reduce window(i, j) such that j + 1 - i == s1.size() while the window still contains all chars in s1 by moving i, return true;
- if windows no longer contain all chars in s1, keep moving j forward;
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<int> cnt(256,0);
for( char c:s1){
cnt[c]++;
}
int left=s1.size();
for(int i=0,j=0;j<s2.size();j++){
if(cnt[s2[j]]-- >0){
left--;
}
while(left==0){
if(j-i+1==s1.size()) return true;
if(++cnt[s2[i++]]>0) left++;
}
}
return false;
}
};
