【滑动窗口】剑指 Offer II 014. 字符串中的变位词

剑指 Offer II 014. 字符串中的变位词

题目：

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

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

原题链接：

014. 字符串中的变位词

示例1：

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

示例2：

输入: s1= “ab” s2 = “eidboaoo”
输出: False

题解：

使用滑动窗口思想，这里维护两个数组代表窗口，让窗口1固定，表示字符串s1的字符，窗口2表示字符串s2，刚开始对窗口的初始化为字符串s1的长度，每次进一个字符出一个字符，比较两个窗口，如果相同，则返回真，遍历完成后，还没有返回真，则为假。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) return false;
        vector<int> cnt1(26);
        vector<int> cnt2(26);

        for (int i = 0; i < n; ++i) {
            ++cnt1[s1[i] - 'a'];
            ++cnt2[s2[i] - 'a'];
        }
        if (cnt1 == cnt2) return true;

        for (int i = n; i < m; ++i) {
            ++cnt2[s2[i] - 'a'];
            --cnt2[s2[i - n] - 'a'];
            if (cnt1 == cnt2) {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题解2：双指针

在保证区间长度为 n 的情况下，去考察是否存在一个区间使得 cnt 的值全为 0。

反过来，还可以在保证cnt 的值不为正的情况下，去考察是否存在一个区间，其长度恰好为 n。

初始时，仅统计s1​ 中的字符，则 cnt 的值均不为正，且元素值之和为 −n。

然后用两个指针left 和right 表示考察的区间[left,right]。right 每向右移动一次，就统计一次进入区间的字符 x。为保证cnt 的值不为正，若此时cnt[x]>0，则向右移动左指针，减少离开区间的字符的 cnt 值直到cnt[x]≤0。

注意到 left,right的长度每增加 1，cnt 的元素值之和就增加 1。当 [left,right] 的长度恰好为 n 时，就意味着cnt 的元素值之和为 0。由于cnt 的值不为正，元素值之和为0 就意味着所有元素均为 0，这样我们就找到了一个目标子串。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        vector<int> cnt(26);
        for (int i = 0; i < n; ++i) {
            --cnt[s1[i] - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2[right] - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2[left] - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27