567. 字符串的排列
567. 字符串的排列
🟠 🔖 哈希表
双指针
字符串
滑动窗口
🔗 力扣
LeetCode
题目
Given two strings s1
and s2
, return true
ifs2
contains a permutation ofs1
, orfalse
otherwise.
In other words, return true
if one of s1
's permutations is the substring of s2
.
Example 1:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:
1 <= s1.length, s2.length <= 10^4
s1
ands2
consist of lowercase English letters.
题目大意
给你两个字符串 s1
和 s2
,写一个函数来判断 s2
是否包含 s1
的排列。如果是,返回 true
;否则,返回 false
。
换句话说,s1
的排列之一是 s2
的 子串 。
解题思路
这种题目,是明显的滑动窗口算法,相当给你一个 s1
和一个 s2
,请问你 s2
中是否存在一个子串,包含 s1
中所有字符且不包含其他字符。
滑动窗口算法的思路是这样:
- 使用双指针中的左右指针,初始化
left = right = 0
,把索引左闭右开区间[left, right)
称为一个「窗口」; - 不断地增加
right
指针扩大窗口[left, right)
,直到窗口中的字符串符合要求(包含了s1.length
个字符); - 停止增加
right
,转而不断增加left
指针缩小窗口[left, right)
,直到窗口中的字符串不再符合要求(不包含s1.length
个字符了);同时,每次增加left
,都要更新一轮结果; - 重复第 2 和第 3 步,直到
right
到达字符串s2
的尽头;
详细的滑动窗口答题框架讲解,可阅读 《3.11 滑动窗口》。
复杂度分析
- 时间复杂度:
O(n + m)
,其中n
是s2
的长度,m
是s1
的长度。- 初始化
need
字典需要遍历字符串s1
,时间复杂度是O(m)
; - 滑动窗口遍历
s2
,外层的while
循环遍历字符串s2
,且每次迭代移动右边界right
,最多遍历n
次; - 内层
while
循环在窗口大小达到s1.length
时才会触发,但它总共只移动left
指针n
次,因此总的移动操作是线性的。
- 初始化
- 空间复杂度:
O(1)
,need
和window
字典的大小最多是英文字母的数量(26 个字母),所以它们的空间复杂度是O(1)
,其他变量的存储是常数空间。
代码
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var checkInclusion = function (s1, s2) {
let window = {},
need = {};
for (let i of s1) {
need[i] = (need[i] || 0) + 1;
}
let left = 0,
right = 0,
valid = 0;
while (right < s2.length) {
let c = s2[right];
right++;
// 进行窗口内数据的一系列更新
if (need[c]) {
window[c] = (window[c] || 0) + 1;
if (window[c] == need[c]) {
valid += 1;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= s1.length) {
// 在这里判断是否找到了合法的子串
if (valid == Object.keys(need).length) {
return true;
}
let d = s2[left];
left++;
// 进行窗口内数据的一系列更新
if (need[d]) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
// 未找到符合条件的子串
return false;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
76 | 最小覆盖子串 | [✓] | 哈希表 字符串 滑动窗口 | |
438 | 找到字符串中所有字母异位词 | [✓] | 哈希表 字符串 滑动窗口 |