首页 🍒LeetCode,🐶算法

题目

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。

换句话说,第一个字符串的排列之一是第二个字符串的子串。

示例1:

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

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False
 

注意:

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

使用两个map来操作
mp0用来记录s1中字符种类和数目,mp1用来记录s2中滑动窗口的字符种类和数目,用两个指针来规定s2中窗口起末位置。
当mp0 == mp1时返回true。
如果此窗口不符合mp0 == mp1则left, right一起向右移动,并且让mp1[s2[left]]--,让mp1[s2[right]]++,这里需要注意:如果mp1[s2[left]]--后mp1[s2[left]] == 0则应该把s2[left]从mp1中去掉,因为等于0和不存在是不一样的

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        map<char, int> mp0;
        map<char, int> mp1;
        if (s2.size() == 0) {
            return false;
        }
        if (s1.size() == 0) {
            return true;
        }
        int count = 0, left = 0, right = s1.size() - 1;
        for (int i = 0; i < s1.size(); i++) {
            mp0[s1[i]]++;
        }
        for (int i = left; i <= right && i < s2.size(); i++) {
            mp1[s2[i]]++;
        }
        while (right < s2.size() - 1) {
            if (mp0 == mp1) return true;
            mp1[s2[left]]--;
            if (mp1[s2[left]] == 0) { 
                for (auto it = mp1.begin(); it != mp1.end(); it++) {
                    if (it->first == s2[left]) {
                        mp1.erase(it);
                        break;
                    }
                }
            }
            if (right < s2.size() - 1) right++;
            left++;
            mp1[s2[right]]++;
        }
        if (mp0 == mp1) return true;
        return false;
    }
};



文章评论