blob: f4e09f35dae7c199c8751cb71efc9d4e39dabd57 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
// 567. Permutation in String
#include "leetcode.h"
/*
* given two strings 's1 s2' return true if 's2' contains a permutation of 's1'
* or false otherwise. in other words, return true if one of 's1's permutations
* is in the substring of 's2'
*/
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s2.size() < s1.size())
return false;
vector<int> freq1(26, 0), freq2(26, 0);
for (char c : s1)
freq1[c - 'a']++;
int i = 0, j = 0;
while (j < s2.size()) {
freq2[s2[j] - 'a']++;
if (j - i + 1 == s1.size())
if (cmp(freq1, freq2))
return true;
if (j - i + 1 < s1.size())
j++;
else {
freq2[s2[i] - 'a']--;
i++, j++;
}
}
return false;
}
private:
bool cmp(vector<int> a, vector<int> b) {
for (int i = 0; i < 26; i++)
if (a[i] != b[i])
return false;
return true;
}
};
int main() {
Solution obj;
cout << obj.checkInclusion("ab", "eidbaooo") << endl; // expect: 1
cout << obj.checkInclusion("ab", "eidboaoo") << endl; // expect: 0
}
|