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