字符串的排列：滑动窗口

这道题主要学了频次数组的使用，巩固滑动窗口。
好在 STL 的 vector 有 operator== 重载使得比较数组是否相等很容易，省去了很多麻烦。

题目

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

题解

只需要判断 s2 是否包含 s1 的排列，不计较顺序可以用频次数组来解决。字符串的子串考虑滑动窗口。
显然需要两个频次数组：s1 单词的频次，s2 窗口的频次。用 STL 的 vector 更好。

 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


bool checkInclusion(std::string s1, std::string s2)
{
    std::vector<int> window(26, 0); // 当前窗口的字符频次
    std::vector<int> need(26, 0);   // s1 的字符频次
    int left, right, i;

    if (s1.length() > s2.length())
        return false;

    // 遍历 s1 填好需求数组
    for (i = 0; i < s1.length(); i++)
        need[s1[i] - 'a'] += 1;

    left = 0;
    for (right = 0; right < s2.length(); right++)
    {
        window[s2[right] - 'a'] += 1;

        if (right - left + 1 > s1.length())
        {
            window[s2[left] - 'a'] -= 1;
            left++;
        }
        if (window == need)
            return true;
    }
    return false;
}