567. 字符串的排列
题目描述
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”).
示例2: 输入: s1= “ab” s2 = “eidboaoo” 输出: False
注意： 输入的字符串只包含小写字母 两个字符串的长度都在 [1, 10,000] 之间
解题思路
因为无所谓子字符串的排列顺序，所以可以使用打表，统计字符串中字符出现次数使用滑动窗口，比较两个子字符串是否匹配，不匹配的话，只要移动首尾两个字符
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if(s1.length()>s2.length()) return false;
int book[26]={0};
int len1=s1.length(),len2=s2.length();
for(int i=0;i<s1.length();i++){
book[s1[i]-'a']++;
book[s2[i]-'a']--;
}
bool flag=true;
for(int i=0;i<26;i++){
if(book[i]!=0){
flag=false;
break;
}
}
if(flag==true){
return true;
}
book[s2[0]-'a']++;
for(int i=1;i<=len2-len1;i++){
flag=true;
book[s2[i+len1-1]-'a']--;
for(int k=0;k<26;k++){
if(book[k]!=0){
flag=false;
break;
}
}
if(flag==true) return true;
book[s2[i]-'a']++;
}
return false;
}
};
