字符串中的变位词

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

1.静态滑动窗口1

由于知道目标字符串的长度，故可以通过暴力枚举的方式（一个静态的滑动窗口）来枚举出所有的情况，

并对枚举的每种情况进行字母数量的统计，利用哈希表实现字母数量的统计，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool checkInclusion(string pattern, string text) {
        for (int i = 0, j = i + pattern.length(); j <= text.length(); ++i, ++j) {
            int flag = 0;
            vector<int> cnt(26);
            for (int k = 0; k < pattern.length(); ++k) cnt[pattern[k] - 'a']++;//查找目标的字母数量统计
            for (int k = i; k < j; ++k) cnt[text[k] - 'a']--;//遍历的字符串的字母数量统计
            for (int i = 0; i < 26; ++i) if (cnt[i] != 0) flag = 1;//判断字母数量是否相同
            if (flag) continue;
            return true;
        }
        return false;
    }
};
  • 勉强能过，时间复杂度与空间复杂度都很高。

2.静态滑动窗口2

对每次的字母数量判断操作进行修改，对边界值进行加入与减出操作，思路没有问题的，先做记录在此。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool checkInclusion(string pattern, string text) {
        if (pattern.length() > text.length()) return false;
        //1.字母计数数组
        vector<int> cnt1(26), cnt2(26);

        //2.滑动窗口初始化
        for (int i = 0; i < pattern.length(); ++i) {
            cnt1[pattern[i] - 'a']++;
            cnt2[text[i] - 'a']++;
        }
        if (cnt1 == cnt2) return true;

        //3.滑动窗口开始移动
        for (int i = 0, j = i + pattern.length(); j < text.length(); ++i, ++j) {
            cnt2[text[i] - 'a']--;
            cnt2[text[j] - 'a']++;
            if (cnt1 == cnt2) return true;
        }
        return false;
    }
};

思考：既然使用一个vector<int> cnt;数组就能替代unordered_map，那么unordered_map存在的意义是什么？

并且在将unordered_map换成vector数组进行计数，可以达到更低的时间复杂度与空间复杂度。

3.静态滑动窗口3

注意到每次窗口滑动时，只统计了一进一出两个字符，却比较了整个cnt数组，

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
28
29
30
31
32
33
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) return false;

        //1.滑动窗口初始化
        vector<int> cnt(26);
        for (int i = 0; i < n; ++i) {
            --cnt[s1[i] - 'a'];
            ++cnt[s2[i] - 'a'];
        }
        int diff = 0;
        for (int c: cnt) if (c != 0) ++diff;
        if (diff == 0) return true;

        //2.滑动窗口开始移动
        for (int i = 0, j = i + n; j < m; ++i, ++j) {
            int x = s2[j] - 'a', y = s2[i] - 'a';
            if (x == y) continue;

            if (cnt[x] == 0) ++diff;
            ++cnt[x];
            if (cnt[x] == 0) --diff;
            if (cnt[y] == 0) ++diff;
            --cnt[y];
            if (cnt[y] == 0) --diff;

            if (diff == 0) return true;
        }
        return false;
    }
};
  • 时间复杂度：$O(n+m+|E|)$ ，其中n是字符串s1长度、m是字符串s2长度，E是字符集，这道题中字符集是小写字母$|E|$ = 26
  • 空间复杂度：$O(|E|)$

4.双指针

  • 静态滑动窗口的思路：在保证区间长度为 $n$ 的情况下，去考察是否存在一个区间使得 $cnt$ 的值全为 0，
  • 反过来，还可以在保证 $cnt$ 的值不为正的情况下，去考察是否存在一个区间，其长度恰好为 $n$

双指针思路：

  1. 统计pattern中的字母数量：
    • 初始时仅统计s1中的字符，则 cnt 的值均不为正，且元素值之和为 −n
  2. 在text中使用滑动窗口匹配合适的答案：
    • 然后用两个指针 i 和 j 表示考察的区间 [i, j]。j 每向右移动一次，就统计一次进入区间的字符 x。
    • 为保证cnt的值不为正，若此时cnt[x]>0，则左指针向右移动，减少离开区间的字符的cnt值直到 cnt[x]≤0。
    • 注意到[i, j]的长度每增加1，cnt的元素值之和就增加1。当[i, j]的长度恰好为n时，就意味着cnt的元素值之和为0。
    • 由于cnt的值不为正，元素值之和为0就意味着所有元素均为0，这样我们就找到了一个目标子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool checkInclusion(string pattern, string text) {
        if (pattern.length() > text.length()) return false;

        //1.统计pattern中的字母数量
        vector<int> cnt(26);
        for (int i = 0; i < pattern.length(); ++i) cnt[pattern[i] - 'a']--;

        //2.在text中使用滑动窗口匹配合适的答案
        for (int i = 0, j = 0; j < text.length(); ++j) {
            int x = text[j] - 'a';
            cnt[x]++;
            while (cnt[x] > 0) {
                cnt[text[i] - 'a']--;
                i++;
            }
            if (j - i + 1 == pattern.length()) return true;
        }
        return false;
    }
};
  • 时间复杂度：$O(n+m+|E|)$ ，创建 $cnt$ 需要 $O(|E|)$ 的时间，遍历s1需要 $O(n)$ 的时间，双指针遍历s2由于left与right都会移动，需要 $O(m)$ 时间
  • 空间复杂度：$O(|E|)$