leetcode 567. Permutation in String 寻找子串 + 滑动窗口-蒲公英云

leetcode 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].

本题题意很简单，直接使用一个滑动窗口来做遍历即可

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
using namespace std;
class Solution 
{
public:
    bool checkInclusion(string s1, string s2) 
    {
        if (s1.length() > s2.length())
            return false;
        vector<int> m1(26), m2(26);
        for (int i = 0; i < s2.length(); i++)
        {
            if (i < s1.length())
            {
                m1[s1[i] - 'a']++;
                m2[s2[i] - 'a']++;
            }
            else
            {
                if (m1 == m2)
                    return true;
                m2[s2[i] - 'a']++;
                m2[s2[i-s1.length()] - 'a']--;
            }
        }
        if (m1 == m2)
            return true;
        else
            return false;
    }
};