[leetcode] 567. Permutation in String

567. Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:
Input:s1 = “ab” s2 = “eidbaooo”
Output:True
Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:
Input:s1= “ab” s2 = “eidboaoo”
Output: False
Note:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

题目：

给定两个字符串s1和s2，判断s1的排列是否在s2中。

解题思路

方法1：最简单最暴力的方法其实就是找到s1的所有全排列，然后在s2中查找是否这些全排列字符串在s2中。但是这种方法耗时太大，会导致超时。
方法2：滑动窗口
其实不需要找到s1的全排列，因为我们只需要考虑s2中是否包含s1中同样个数的字符，并且这些字符是连在一起的就行了。因此，我们可以使用一个滑动窗口，在s2上滑动。在这个滑动窗口中的字符及其个数是否刚好等于s1中的字符及其个数，此外滑动窗口保证了这些字符是连在一起的。

bool checkInclusion(string s1, string s2) {
    int len1 = s1.size();
    int len2 = s2.size();
    if (len1 > len2) return false;
    vector<int> maps1(26), maps2(26);
    for (int i = 0; i < len1; ++i)
    {
        maps1[s1[i] - 'a'] ++;
        maps2[s2[i] - 'a'] ++;
    }
    if (maps1 == maps2) return true;
    for (int i = 0; i + len1 < len2; ++i)
    {
        maps2[s2[i] - 'a'] --;
        maps2[s2[i + len1] - 'a'] ++;
        if (maps1 == maps2) return true;
    }
    return false;
}