-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathPermutation in String
34 lines (25 loc) · 973 Bytes
/
Permutation in String
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
// Given two strings s1 and 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 the substring of s2.
// Eg: s1 = 'ab', s2 = 'eidbaooo'
// Ans = True
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
net = dict()
for c in s1:
net[c] = net.get(c, 0) + 1
wanted = 0
i = 0
for j in range(len(s2)):
if s2[j] in net:
net[s2[j]] -= 1
if net[s2[j]] == 0:
wanted += 1
if wanted == len(net):
return True // s1 exists in s2
if (j - i + 1) == len(s1):
if s2[i] in net:
if net[s2[i]] == 0:
wanted -= 1
net[s2[i]] += 1
i += 1
return False