567 Permutation in String
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
Input:s1= "ab" s2 = "eidboaoo"
Output: False
Note: 1. The input strings only contain lower case letters. 2. The length of both given strings is in range [1, 10,000].
Brute Force Approach: Every substring of length |s1| in |s2| and find at least one instance of where the sorted substring == sorted s1.
Time Complexity: Let s1 be len(s1) and s2 be len(s2). O((s1-s2)*s1logs1 + s1(s1-s2)) for sorting each substring and string comparison.
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
sorted_s1 = sorted(s1)
go_till = len(s2) - len(s1) + 1
for i in range(0, go_till):
if sorted_s1 == sorted(s2[i:i+len(s1)]):
return True
return False
Last modified 3yr ago