题目描述 字符串的排列
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
解题思路
1、本题的关键在于注意到题目中说“只包括小写字母”,所以可以想到创建一个数组长度是26, 然后从0 - 25代表一段长度字符串中个字母出现的次数,这个数组可以叫做“字母数组”。
2、s1 是字串,所以可以将整个s1 生成一个“字母数组”,然后与 s2 的滑动窗口中的“字母数组”进行 比较,如果出现 “字母数组”相等的情况,则可以认定 s1 是 s2 的子串。
3、对于 s2 的滑动窗口的 “字母数组”,下一个滑动窗口的 “字母数组”和上一个滑动窗口的 “字母数组” 相比较,只有滑动窗口首尾两个元素有变化,所以只要改变“字母数组”头尾对应元素的数量即可得到下一个“字母数组”。
代码
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int len1 = s1.length();
int len2 = s2.length();
int wordsnum1[26]={0};
int wordsnum2[26]={0};
if(len2 < len1) return false;
for(int i=0; i<len1; ++i){
++wordsnum1[s1[i]-'a'];
}
for(int i=0; i<len2-len1+1; ++i){
bool ctn = false;
if(i == 0){
for(int j=0; j<len1; ++j){
++wordsnum2[s2[i+j]-'a'];
}
}else{
--wordsnum2[s2[i-1]-'a'];
++wordsnum2[s2[i+len1-1]-'a'];
}
for(int j=0; j<26; ++j){
if(wordsnum1[j] != wordsnum2[j]){
ctn = true;
break;
}
}
if(!ctn) return true;
}
return false;
}
};