LeetCode 567、字符串的排列

567、字符串的排列

1）题目描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

• 1 <= s1.length, s2.length <= 10^4
• s1 和 s2 仅包含小写字母

2）分析

滑窗，哈希。使用两个表，一个用来记录s1中各个字符出现的次数，另一个用来记录s2中与s1等长子串中各个字符出现的次数。比较两个哈希表是否相等，若相等返回true，不相等则s2子串向后滑动一个字符，再比较。直到s2尾部结束。若结束还未出现相等，返回false。

3）C++代码

class Solution {
    
public:
    bool checkInclusion(string s1, string s2) {
    
        if(s1.length()>s2.length())
            return false;
        vector<int> hsahS1(26,0),hashS2(26,0);

        for(int i=0;i<s1.length();i++){
    
            hsahS1[s1[i]-'a']++;
            hashS2[s2[i]-'a']++;
        }
        if(hsahS1==hashS2)
            return true;

        for(int i=s1.length();i<s2.length();i++){
    
            hashS2[s2[i]-'a']++;
            hashS2[s2[i-s1.length()]-'a']--;
            if(hsahS1==hashS2)
                return true;
        }
        return false;
    }
};