跳至主要內容

567. 字符串的排列


567. 字符串的排列

🟠   🔖  哈希表 双指针 字符串 滑动窗口  🔗 力扣open in new window LeetCodeopen in new window

题目

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 and s2 consist of lowercase English letters.

题目大意

给你两个字符串 s1s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false

换句话说,s1 的排列之一是 s2子串

解题思路

这种题目,是明显的滑动窗口算法,相当给你一个 s1 和一个 s2,请问你 s2 中是否存在一个子串,包含 s1 中所有字符且不包含其他字符。

滑动窗口算法的思路是这样:

  1. 使用双指针中的左右指针,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」;
  2. 不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 s1.length 个字符);
  3. 停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 s1.length 个字符了);同时,每次增加 left,都要更新一轮结果;
  4. 重复第 2 和第 3 步,直到 right 到达字符串 s2 的尽头;

详细的滑动窗口答题框架讲解,可阅读 《3.11 滑动窗口》

复杂度分析

  • 时间复杂度O(n + m),其中 ns2 的长度,ms1 的长度。
    • 初始化 need 字典需要遍历字符串 s1,时间复杂度是 O(m)
    • 滑动窗口遍历 s2,外层的 while 循环遍历字符串 s2,且每次迭代移动右边界 right,最多遍历 n 次;
    • 内层 while 循环在窗口大小达到 s1.length 时才会触发,但它总共只移动 left 指针 n 次,因此总的移动操作是线性的。
  • 空间复杂度O(1)needwindow 字典的大小最多是英文字母的数量(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最小覆盖子串[✓]哈希表 字符串 滑动窗口🔴🀄️open in new window 🔗open in new window
438找到字符串中所有字母异位词[✓]哈希表 字符串 滑动窗口🟠🀄️open in new window 🔗open in new window