31 lines
860 B
Python
31 lines
860 B
Python
|
# Time: O(S1 · S2) ; S2 is len(s1) and S2 is len(S2)
|
||
|
|
# Space: O(S2 · 26)
|
||
|
|
|
||
|
|
from collections import Counter
|
||
|
|
|
||
|
|
class Solution:
|
||
|
|
def checkInclusion(self, s1: str, s2: str) -> bool:
|
||
|
|
if len(s1) > len(s2): return False
|
||
|
|
|
||
|
|
if len(s1) == len(s2):
|
||
|
|
return Counter(s1) == Counter(s2)
|
||
|
|
|
||
|
|
s1_counter = Counter(s1)
|
||
|
|
|
||
|
|
target_length = len(s1)
|
||
|
|
end = target_length - 1
|
||
|
|
|
||
|
|
while end < len(s2):
|
||
|
|
start = end - target_length + 1
|
||
|
|
curr_substring = s2[start:end + 1]
|
||
|
|
|
||
|
|
# Check if counters match for the given substring
|
||
|
|
# indicated by start:end with a length of target_length
|
||
|
|
if s1_counter == Counter(curr_substring):
|
||
|
|
return True
|
||
|
|
|
||
|
|
end += 1
|
||
|
|
|
||
|
|
return False
|
||
|
|
|
||
|
|
|