LeetCode[中等] 438. 找到字符串中所有字母异位词
给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
思路:滑动窗口
- s包含p的异位词 ——> 则s.Length > p.Length;反之,s不包含p的异位词,返回空数组。
- s.Length >= p.Length,需要遍历 s 的每个长度为 p 长度的子字符串,判断是否存在子字符串是 p 的异位词。比较每个字符的出现次数,判断每个子字符串是否为 p 的异位词。
- 首先遍历 p 计算每个字符的出现次数,然后遍历 s 的首个子字符串并计算每个字符的出现次数。
- 每次将子字符串的下标范围向右移动一位,则有一个字符移出子字符串,有一个字符移入子字符串,更新子字符串中这两个字符的出现次数之后,比较子字符串中的每个字符的出现次数是否与 p 中的每个字符的出现次数相同。
public class Solution { public IList<int> FindAnagrams(string s, string p) { IList<int> startIndices = new List<int>(); int sLength = s.Length, pLength = p.Length; if(sLength < pLength) return startIndices; int[] sCounts = new int[26]; int[] pCounts = new int[26]; for(int i = 0; i < pLength; i++) { char c1 = s[i]; sCounts[c1 - 'a']++; char c2 = p[i]; pCounts[c2 - 'a']++; } if (CheckEqual(sCounts, pCounts)) { startIndices.Add(0); } for(int i = pLength; i < sLength; i++) { char prev = s[i - pLength];//上一次的窗口第一个元素 sCounts[prev - 'a']--; char curr = s[i];//末尾元素 sCounts[curr - 'a']++; if (CheckEqual(sCounts, pCounts)) { startIndices.Add(i - pLength + 1); } } return startIndices; } public bool CheckEqual(int[] sCounts, int[] pCounts) { for (int i = 0; i < 26; i++) { if (sCounts[i] != pCounts[i]) { return false; } } return true; } }
复杂度分析
- 时间复杂度:O((m+n)×∣Σ∣),其中 m 和 n 分别是字符串 s 和 p 的长度,Σ 是字符集,这道题中 Σ 是全部小写英语字母,∣Σ∣=26。只有当 s 的长度大于等于 p 的长度时才需要遍历字符串 s 寻找 p 的异位词,需要遍历字符串 s 和 p 各一次,对于每个子字符串需要 O(∣Σ∣) 的时间判断是否为 p 的异位词。
-
空间复杂度:O(∣Σ∣),其中 Σ 是字符集,这道题中 Σ 是全部小写英语字母,∣Σ∣=26。记录 p 和 s 中每个字母的出现次数需要 O(∣Σ∣) 的空间。