给定两个字符串s1和 s2，写一个函数来判断s2 是否包含 s1的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例：
输入:
s1 = "ab" s2 = "eidbaooo"
输出:True
解释:s2包含s1的排列之一 ("ba").
来源：LeetCode 第567题
相关企业：
| 公司 | 出现时间 |
|---|---|
| 字节跳动 | xxx |
解法：滑动窗口 + 哈希表
时间复杂度：O(n)
空间复杂度：O(n)
思路：维护窗口大小为len(s1)的两个指针left和right，在字符串s2上滑动，判断窗口内的hash表是否和s1的hash表一致。
代码：
def checkInclusion(self, s1: str, s2: str) -> bool:
char_dic = collections.Counter(s1)
left, right = 0, len(s1) - 1
while right < len(s2):
if collections.Counter(s2[left : right + 1]) == char_dic:
return True
left += 1
right += 1
return False
网友评论