Description

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.

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


Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

Solutions

1. Sliding Window

自己实现的版本不优雅：

# Time Complexity: O(l1+l2)
# Space Complexity: O(l1+l2)
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
n1, n2 = len(s1), len(s2)
d1 = collections.defaultdict()
d2 = collections.defaultdict()

for i in range(n1):
d1[s1[i]] = d1.get(s1[i], 0)
d1[s1[i]] += 1
d2[s2[i]] = d2.get(s2[i], 0)
d2[s2[i]] += 1

if d1 == d2:
return True

for i in range(n1, n2):
d2[s2[i]] = d2.get(s2[i], 0)
d2[s2[i]] += 1
d2[s2[i-n1]] -= 1
if d2[s2[i-n1]] == 0:
d2.pop(s2[i-n1])
if d1 == d2:
return True

return False
# Runtime: 84 ms, faster than 51.79% of Python3 online submissions for Permutation in String.
# Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Permutation in String.


直接设定 26 个字母的字典，比来回增删操作会快很多！

# Time Complexity: O(l1+l2)
# Space Complexity: O(l1+l2)
import string

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1)>len(s2):
return False
s1_freq = dict.fromkeys(string.ascii_lowercase, 0)
s2_freq = dict.fromkeys(string.ascii_lowercase, 0)
for c in s1:
s1_freq[c]+=1
k = len(s1)
for i in range(k):
s2_freq[s2[i]] += 1
for i in range(k, len(s2)+1):
if s2_freq == s1_freq:
return True
elif i< len(s2):
s2_freq[s2[i-k]]-=1
s2_freq[s2[i]]+=1
else:
return False
return False
# Runtime: 52 ms, faster than 98.58% of Python3 online submissions for Permutation in String.
# Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Permutation in String.


2. Sliding Window - Two Pointers

用双指针发现更加复杂了：

# Time Complexity: O(l1+l2)
# Space Complexity: O(l1+l2)
import string
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
n1, n2 = len(s1), len(s2)
l = 0
m = dict.fromkeys(string.ascii_lowercase, 0)

for c in s1:
m[c] += 1

cnt = n1
for r in range(n2):
if m[s2[r]] > 0:
cnt -= 1
m[s2[r]] -= 1
while cnt == 0:
if r - l + 1 == n1:
return True
m[s2[l]] += 1
if m[s2[l]] > 0:
cnt += 1
l += 1
return False
# Runtime: 52 ms, faster than 98.58% of Python3 online submissions for Permutation in String.
# Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Permutation in String.