-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDay18.cpp
55 lines (38 loc) · 1.04 KB
/
Day18.cpp
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
48
49
50
51
52
53
54
55
// using slidding window technique
// https://www.youtube.com/watch?v=MPtX8pGYHCs
class Solution {
public:
bool checkInclusion(string patt, string original) {
if( patt.length() > original.length() ) return false;
int patt_freq[26];
int original_freq[26];
memset( patt_freq, false, sizeof patt_freq );
memset( original_freq, false, sizeof original_freq );
for(int i = 0 ; i < patt.length() ; i++)
{
int x = patt[i] - 'a';
patt_freq[x]++;
}
for(int i = 0 ; i < original.length() ; i++)
{
original_freq[ original[i]-'a' ]++;
if( i >= patt.length() )
{
original_freq[ original[i - patt.length()]-'a' ]--;
}
int cnt = 0 ;
for(int i = 0 ; i <26 ; i++)
{
if(original_freq[i]==patt_freq[i])
{
cnt++;
}
}
if(cnt==26)
{
return true;
}
}
return false;
}
};