问题
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.
例子
Input:s1 = "ab" s2 = "eidbaooo"
Output:True
**Explanation: **s2 contains one permutation of s1 ("ba").
Input:s1= "ab" s2 = "eidboaoo"
Output: False
分析
开辟一个大小为26的滑动窗口，保存字符串的字符元素出现的次数，字符串的长度和s1的长度一致。
例如s1=ab, s2=eibaooo.则s1对应的滑动窗口为：
11000000000000000000000000
s2前两个字符对应的滑动窗口为：
00001000100000000000000000
首先用s1和s2的前s1长度段初始化滑动窗口，s1出现的字符次数减一，s2的前s1长度段出现的字符次数加一。然后滑动窗口从s2的左边向右边滑动。每滑动一次，把从滑动窗口左侧滑出的字符的次数减一，把从滑动窗口右侧滑入的字符的次数加一。统计滑动窗口次数为0的个数，如果等于26则说明在s2找到了s1的一个排列。
要点
- 使用map来表示字符串的信息（map可以用数组模拟，提高效率）；
- 滑动窗口。
时间复杂度
O(n), n是s2的长度
空间复杂度
O(1)
代码
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<int> count(26, 0);
for (int i = 0; i < s1.size(); i++) {
count[s1[i] - 'a']--;
count[s2[i] - 'a']++;
}
int zeroNum = 0;
for (int i = 0; i < 26; i++)
zeroNum += count[i] == 0 ? 1 : 0;
if (zeroNum == 26) return true;
for (int i = s1.size(); i < s2.size(); i++) {
count[s2[i] - 'a']++;
if (count[s2[i] - 'a'] == 0) zeroNum++;
if (count[s2[i] - 'a'] == 1) zeroNum--;
count[s2[i - s1.size()] - 'a']--;
if (count[s2[i - s1.size()] - 'a'] == 0) zeroNum++;
if (count[s2[i - s1.size()] - 'a'] == -1) zeroNum--;
if (zeroNum == 26) return true;
}
return false;
}
};
