leetcode 567. Permutation in String 寻找子串 + 滑动窗口

太过爱你忘了你带给我的痛 2022-06-03 04:23 142阅读 0赞

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;
        }
    };