173 - 567 字符串的排列 027
题目
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo" 输出: False
注意:
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
解答
https://leetcode.com/problems/permutation-in-string/discuss/102588/Java-Solution-Sliding-Window
如果s2要包含s1的排列,那么s1中所有的字母,都得出现在s2里面
因此可以用一个数组来记录出现的频率
可以用一个窗口,即截取s2的一部分,
class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
def getHash(s): # 拿到哈希
hashTable = dict()
for c in s:
if c not in hashTable:
hashTable[c] = 0
hashTable[c] += 1
return hashTable
lenS1 = len(s1)
lenS2 = len(s2)
lenDiff = lenS2 - lenS1
if lenDiff < 0:
return False
head, tail = 0, lenS1 - 1
hashS1 = getHash(s1)
hashS2 = getHash(s2[head: tail + 1])
while tail < lenS2:
if hashS1 == hashS2:
return True
tail += 1
if tail == lenS2:
break
if s2[tail] not in hashS1:
if tail + 1 + lenS1 >= lenS2:
break
else:
head = tail + 1
tail = head + lenS1 - 1
hashS2 = getHash(s2[head: tail + 1])
else:
if s2[tail] not in hashS2:
hashS2[s2[tail]] = 0
hashS2[s2[tail]] += 1
hashS2[s2[head]] -= 1
if hashS2[s2[head]] == 0: #这里需要注意的是,如果这里没有了这个数,则需要删除这个键值
del hashS2[s2[head]]
head += 1
return False
Runtime: 56 ms, faster than 95.90% 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.
class Solution(object):
def checkInclusion(self, s1, s2):
A = [ord(x)-ord('a')for x in s1]
B = [ord(x)-ord('a')for x in s2]
target = [0]*26
for x in A:
target[x] += 1
window = [0]*26
for i, x in enumerate(B):
window[x] += 1
if i >= len(A):
window[B[i-len(A)]] -= 1
if window == target:
return True
return False
Runtime: 72 ms, faster than 69.88% 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.
Last updated
Was this helpful?