Saturday, August 22, 2020

567. Permutation in String -----------M

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

 

Constraints:

  • The input strings only contain lower case letters.
  • The length of both given strings is in range [1, 10,000].


A: 

就是一个个对比啊。记录每个char的数量

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> V1(26,0);
        vector<int> V2(26,0);
        int n1 = s1.length(), n2 = s2.length();
        if(n2<n1)
            return false;
        for(int i =0;i<n1;i++){
            V1[s1[i]-'a']++;
            V2[s2[i]-'a']++;
        }
        if(helper(V1,V2))
            return true;
        for(int i =n1;i<n2;i++){
            V2[s2[i]-'a']++;
            V2[s2[i-n1]-'a']--;
            if(helper(V1,V2))
                return true;
        }
        return false;
    }
private:
    bool helper(vector<int> & V1, vector<int> & V2){
        for(int i =0;i<26;i++)
            if(V1[i] != V2[i])
                return false;
        return true;
    }
};


No comments:

Post a Comment