567-字符串的排列

LeetCode 567. 字符串的排列

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

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

示例 1：

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

method

维护一个s1.size()大小的滑动窗口，比较窗口内字符的出现次数是否和s1的字符出现次数相等

bool checkInclusion(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    if (m > n) return false;
    vector<int> count1(26);
    vector<int> count2(26);
    for (int i = 0; i < m; i++) {
        count1[s1[i] - 'a']++;
        count2[s2[i] - 'a']++;
    }
    if (count1 == count2) return true;
    for (int i = m; i < n; i++) {
        count2[s2[i - m] - 'a']--;
        count2[s2[i] - 'a']++;
        if (count1 == count2) return true;
    }
    return false;
} 

因为每次只是增加一个字符，减少一个字符，但都要count1和count2整个数组的比较

可以用一个变量distance记录有多少个字符存在差异，然后用一个数组cnt来记录窗口内的字符出现次数与s1的字符出现次数的差值，只要差值不为0，变量distance就为1

• 每次增加一个字符x时，如果原本cnt[x]=0，那么增加字符x后cnt[x]就不为0，所以distance加1，如果加上x后，cnt[x]=0，那distance减1
• 每次减少一个字符y时，如果原本cnt[y]=0，那么减少字符y后cnt[y]就不为0，所以distance加1，如果减去y后，cnt[y]=0，那distance减1
• 如果distance=0，说明没有差异，窗口内的子串和s1的字符时一样的

bool checkInclusion(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    if (m > n) return false;
    vector<int> cnt(26);
    for (int i = 0; i < m; i++) {
        cnt[s1[i] - 'a']--;     // s1减
        cnt[s2[i] - 'a']++;     // s2加
    }
    int distance = 0;
    for (auto n : cnt) {
        if (n != 0) distance++;
    }
    if (distance == 0) return true;
    for (int i = m; i < n; i++) {
        int x = s2[i] - 'a';        // 要加上的
        int y = s2[i - m] - 'a';    // 要减去的
        if (cnt[x] == 0) distance++;
        cnt[x]++;
        if (cnt[x] == 0) distance--;
        if (cnt[y] == 0) distance++;
        cnt[y]--;
        if (cnt[y] == 0) distance--;
        if (distance == 0) return true;
    }
    return false;
}