给两个字符串s1和s2,判断 s2 中是否有s1的排列。 如果是返回 true,否则返回 false。 s1的排列指的是s1字符的不同排列 输入格式:第一行输入字符串 s1 第二行输入字符串 s2。 输出格式:输出小写的true或false 输入: ab eidbaooo 输出: true 备注 1<=s1.length, s2.length < 1000 ;s1和s2仅包含小写字母
时间: 2024-04-09 07:28:57 浏览: 86
可以通过比较两个字符串中每个字符的频次来判断s2中是否包含s1的排列。下面是一种解决方法:
```python
def checkInclusion(s1, s2):
count = [0] * 26
for ch in s1:
count[ord(ch) - ord('a')] += 1
start = 0
end = 0
while end < len(s2):
# 当前字符在s1中存在,减少计数
if count[ord(s2[end]) - ord('a')] > 0:
count[ord(s2[end]) - ord('a')] -= 1
end += 1
# 判断是否找到s1的排列
if end - start == len(s1):
return True
else:
# 当前字符不在s1中,移动窗口起始位置
count[ord(s2[start]) - ord('a')] += 1
start += 1
return False
# 测试样例
s1 = input()
s2 = input()
print(str(checkInclusion(s1, s2)).lower())
```
这段代码使用了滑动窗口的思想,维护一个长度为s1的窗口,在s2上滑动窗口进行比较。其中count数组记录了s1中每个字符的频次,每次移动窗口时,根据当前字符是否在s1中来调整count数组。如果窗口的长度等于s1的长度,并且count数组中的所有元素都变为0,说明找到了s1的排列,返回True。否则,返回False。最后将结果转换为小写形式输出。
阅读全文