题目
1 | 字符串的排列 |
Related Topics: 字符串 滑动窗口
思路
遍历s1所有的排列,判断是否为s2的子串,若是返回true
,否则false
显而易见,仅仅是遍历字符串所有的排列,复杂度就已经是O(n!)
了,阶乘级别,所以肯定行不通。
优化
借鉴[算法训练]LeetCode 3: 无重复字符的最长子串其中滑动窗口的思想
首先假设s1的长度 ≤ s2的长度,这样s1才有可能是s2的子串。
我们构造一个和s1长度相同的窗口,在s2中滑动。
那现在问题就是:如何快速判断s2窗口内的字符串是否为s1的排列组合之一
首先长度相同了,那只要两个字符串内的字符种类及其数量都一致,就肯定是排列之一了。
比如 aab
和 baa
, 都是2个a
,1个b
,aab
是baa
是排列之一。
代码
1 | class Solution: |
如果大家有更好的解法,恳请不吝赐教,谢谢!