==============================================================
Description:
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
s1 and s2 consist of lowercase English letters.
Solution:
class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
counts = collections.Counter(s1)
l = len(s1)
for i in xrange(len(s2)):
if counts[s2[i]] > 0:
l -= 1
counts[s2[i]] -= 1
if l == 0:
return True
start = i + 1 - len(s1)
if start >= 0:
counts[s2[start]] += 1
if counts[s2[start]] > 0:
l += 1
return False
==============================================================
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/permutation-in-string/
Top comments (0)