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.
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:
-
1 <= s1.length, s2.length <= 104 -
s1ands2consist of lowercase English letters.
SOLUTION:
class Solution:
def checkInclusion(self, p: str, s: str) -> bool:
np = len(p)
ns = len(s)
if np > ns:
return False
pctr = [0] * 26
for c in p:
pctr[ord(c) - ord('a')] += 1
sctr = [0] * 26
for i in range(np):
sctr[ord(s[i]) - ord('a')] += 1
i = 0
while i < ns - np:
if pctr == sctr:
return True
sctr[ord(s[i]) - ord('a')] -= 1
sctr[ord(s[i + np]) - ord('a')] += 1
i += 1
if pctr == sctr:
return True
return False
Top comments (0)