题目描述

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

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

样例

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

输入：s1= "ab" s2 = "eidboaoo"
输出：False

限制

• 输入的字符串只包含小写字母。
• 两个字符串的长度都在 [1, 10000] 之间。

算法

(枚举) $O(n + m)$

1. 统计出字符串 s1 中每个字母出现的次数。
2. 在 s2 中依次枚举每一个子串，这样可以实时更新每个子串中各个字母出现的次数。如果发现某个子串中 26 个小写字母的统计出现次数都相等，则宣布存在。

时间复杂度

• 统计字符串 s1 每个字母出现的次数时间复杂度为 $O(n)$。
• s2 中有 $O(m)$ 个子串，实时更新每个子串的各个字母出现次数均摊复杂度为 $O(1)$，每次判断时间复杂度为 $O(1)$。故总时间复杂度为 $O(n + m)$。

空间复杂度

• 仅需要常数的额外空间记录字母的出现次数。

Go 代码

func checkInclusion(s1 string, s2 string) bool {
    var f1, f2 [26]int
    n, m := len(s1), len(s2)

    for i := 0; i < n; i++ {
        f1[conv(s1[i])]++
    }

    for i := 0; i < m; i++ {
        f2[conv(s2[i])]++
        if i + 1 < n {
            continue
        }

        if f1 == f2 {
            return true
        }

        f2[conv(s2[i - n + 1])]--
    }

    return false
}

func conv(c byte) byte {
    return c - 'a'
}

C++ 代码

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        vector<int> st(26, 0), cur(26, 0);
        for (int i = 0; i < n; i++)
            st[s1[i] - 'a']++;

        for (int i = 0; i < m; i++) {
            cur[s2[i] - 'a']++;
            if (i >= n - 1) {
                bool check = true;
                for (int j = 0; j < 26; j++)
                    if (st[j] != cur[j]) {
                        check = false;
                        break;
                    }
                if (check)
                    return true;
                cur[s2[i - n + 1] - 'a']--;
            }
        }
        return false;
    }
};