跳至主要內容

438. 找到字符串中所有字母异位词


438. 找到字符串中所有字母异位词open in new window

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

题目

Given two strings s and p, return an array of all the start indices ofp _' s anagrams in _s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"

Output: [0,6]

Explanation:

The substring with start index = 0 is "cba", which is an anagram of "abc".

The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"

Output: [0,1,2]

Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".

The substring with start index = 1 is "ba", which is an anagram of "ab".

The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

题目大意

给定两个字符串 sp,找到 s 中所有 p异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

解题思路

使用滑动窗口算法,思路如下:

  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)
    • 滑动窗口遍历 s,外层的 while 循环遍历字符串 s,最多遍历 n 次;
    • 内层 if 语句也只是在窗口达到 p.length 时触发,窗口的大小固定为 p.length,每次移动左指针时也是常数时间操作。
  • 空间复杂度O(n)
    • 结果数组 res 最多存储 O(n) 个结果(每个可能的起始索引),在最坏情况下,res 数组可能会存储所有可能的起始索引,导致空间复杂度为 O(n)
    • needwindow 字典的大小最多是英文字母的数量(26 个字母),所以它们的空间复杂度是 O(1),其他变量的存储是常数空间。

代码

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
	let window = {},
		need = {};
	for (let i of p) {
		need[i] = (need[i] || 0) + 1;
	}

	let left = 0,
		right = 0,
		valid = 0,
		// 记录结果
		res = [];

	while (right < s.length) {
		let c = s[right];
		right++;

		// 进行窗口内数据的一系列更新
		if (need[c]) {
			window[c] = (window[c] || 0) + 1;
			if (window[c] == need[c]) {
				valid++;
			}
		}

		// 判断左侧窗口是否要收缩
		if (right - left == p.length) {
			// 当窗口符合条件时,把起始索引加入 res
			if (valid == Object.keys(need).length) {
				res.push(left);
			}

			let d = s[left];
			left++;

			// 进行窗口内数据的一系列更新
			if (need[d]) {
				if (window[d] == need[d]) {
					valid--;
				}
				window[d]--;
			}
		}
	}
	return res;
};

相关题目

题号标题题解标签难度
242有效的字母异位词open in new window[✓]哈希表 字符串 排序
567字符串的排列open in new window[✓]哈希表 双指针 字符串 1+