题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给两个字符串，判断一个字符串，是否包含另一个字符串的排列（也就是对每个字母重新排序的字符串）。

思路分享

  • 本质是求字符串子串的进阶版，但是其实只是滑动窗口+哈希表的基本运用。哈希表记录字母的次数，滑动窗口则按一定规则更新哈希表，直至哈希表的内部元素为空，则算是满足条件。老样子，放下滑动窗口的模板（【Leetcode Daily】1456定长子串中元音的最大数目）。

  • 上面的方法在 C++ 中一般用 unordered_map 来实现，遍历小字符串，记录每个字母对应的个数。然后滑动窗口，对遇到的每个字母做数字减一的操作，减到零就去除元素，字母退出窗口则加一加回去。

  • 不过，陆爻齐还是喜欢把字母映射成 vector 中来处理，由于题目说明了，字母只会是小写字母，因此每个字母可以用减去字母’a’处理映射到[0,25]上。那么怎么记录字母是否剪干净了呢？可以引入一个外部整型变量，该变量在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
29
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> rec_char(26, 0);
        int char_count = 0;
        for (const char a : s1) {
            if (rec_char[a-'a']==0) char_count++;
            rec_char[a-'a']++;
        }
        int win = s1.size();

        for (int i = 0; i < s2.size(); i++) {
            rec_char[s2[i]-'a']--;
            if (rec_char[s2[i]-'a'] == 0) {
                char_count--;
            }

            if (i < win-1) continue; // i 为 win-1 时，窗口开始为 win

            if (char_count == 0) return true;

            rec_char[s2[i-win+1]-'a']++;
            if (rec_char[s2[i-win+1]-'a'] == 1) {
                char_count++;
            }
        }
        return false;
    }
};