leetcode-567. 字符串的排列

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

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

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

y总的做法：

class Solution {
    unordered_map<char, int> map1, map2;

public:
    // 判断 c 是否在map1中，且 map1中和map2中c的数量是否相同
    bool check(char c)
    {
        if (map1.count(c) && map1[c] == map2[c])
            return true;
        return false;
    }

    bool checkInclusion(string s1, string s2) {

        for (auto c : s1) map1[c]++;

        int cnt = 0; // map1和map2中有多少个柱子相等
        for (int left = 0, right = 0; right < s2.size(); right++)
        {
            if (check(s2[right])) cnt --;
            map2[s2[right]]++;
            if (check(s2[right])) cnt ++;

            // 滑动窗口收缩
            if (right - left + 1 > s1.size())
            {
                if (check(s2[left])) cnt -- ;
                map2[s2[left]] --;
                if (check(s2[left])) cnt ++ ;
                
                left++; // 滑动窗口左端点收缩
            }

            if (cnt == map1.size()) // cnt 等于 map1的大小
                return true; 
        }
        return false;
    }
};

没有使用check函数的做法：

class Solution {
public:
    unordered_map<char, int> map1;
    unordered_map<char, int> map2;

    bool check(char c)
    {
        return false;
    }

    bool checkInclusion(string s1, string s2) {
        // 如何判断 str1 是 str2 的 一个排列呢？
        // 2个字符串一定有着相同的char的出现次数。使用哪种数据结构? 哈希表

        for (auto &c : s1) map1[c]++;

        int cnt = 0; // 表示 map1 和 map2 中 有多少个柱子相等
        for (int left = 0, right = 0; right < s2.size(); right++)
        {
            if (map1.count(s2[right]))
            {
                map2[s2[right]]++;
                if (map1[s2[right]] == map2[s2[right]])
                    cnt++;
            }

            if (right - left + 1 > s1.size())
            {
                // if (map1[left_char]) // map1[key]会创建这个key出来，val默认为0。map[key]只是访问val的一种方式，无法判断是否存在。
                if (map1.count(s2[left])) // 使用count()函数判断key是否存在于map1中
                {
                    if (map1[s2[left]] == map2[s2[left]])
                        cnt --;
                    map2[s2[left]]--;
                }
                left ++;
            }
            
            if (cnt == map1.size()) 
                return true;
        }

        return false;
    }
};

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