判断母串是否包含子串的某种排列

本文主要是介绍判断母串是否包含子串的某种排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

给出两个字符串s1 和 s2，判断s2 是否 包含s1的某种排列，如果是，返回True，否则返回False。
输入：s1=‘ab’， s2 = “qwebaei”
输出：True

输入：s1=‘abc’， s2 = “qwebaei”
输出：False

2. 分析

这是一道面试题，要在15min内解决，也并非那么容易。

2.1 贪心思想

我的思想是：某种排列的形态可以用字典存储下来，然后遍历s2的过程就去判断是否能够连续的与s1中的字符匹配上？如果最后待匹配的字符个数为0，那么就返回True；如果遍历到了最后都没匹配完成，那么就返回False。代码如下3.1所示。

2.2 滑动窗口

滑动窗口应该没有上述第一种解法简单。

3. 代码

3.1 代码1

from collections import Counter
def get_res(s1, s2):c_s1 = Counter(s1)remaind = len(s1)for i in range(len(s2)):if c_s1[s2[i]] > 0:remaind-=1c_s1[s2[i]] -= 1if remaind == 0:return Trueelse:c_s1 = Counter(s1)remaind = len(s1)return Falses1 = 'ab'
s2 = "beoasa"
res = get_res(s1, s2)
print(res)

这篇关于判断母串是否包含子串的某种排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---