文章目录
- 1.问题描述
- 2.难度等级
- 3.热门指数
- 4.解题思路
- 方法一：暴力法
- 方法二：滑动窗口
- 参考文献
1.问题描述
给定两个字符串 s 和 p，找到 s 中所有 p 的「异位词」的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1：
代码语言：javascript复制输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2：
代码语言：javascript复制输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。提示：
- s 和 p 仅包含小写字母
2.难度等级
Medium。
3.热门指数
★★★★☆
出题公司：阿里、腾讯、字节。
4.解题思路
方法一：暴力法
容易想到的解法是遍历字符串的所有字符，判断每个字符为起点、长度为 len§ 的子串是否是异位词。
如何判断是否是异位词呢？
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
通过定义，我们可以知道如果构成字符串的字母相同，且每个字母出现的次数相同，则为异位词。
关于数据结构的选择，可以使用 map 存储字母及其出现的个数。
时间复杂度： 这种解法的空间复杂度很高 O(len(s)*len(p))。
空间复杂度： O(len(p))。
注意：这种解法可以通过测试用例，但会超时。
下面以 Golang 为给出实现。
代码语言：javascript复制func findAnagrams(s string, p string) []int {
pmap := make(map[rune]int)
for _, r := range p {
pmap[r] = 1
}
var positions []int
for i := 0; i <= len(s) - len(p); {
smap := make(map[rune]int)
var jump bool
for j := i; j - i < len(p); j {
if _, ok := pmap[rune(s[j])]; !ok {
i = j 1
jump = true
break
}
smap[rune(s[j])] = 1
}
if !jump {
if maps.Equal(pmap, smap) {
positions = append(positions, i)
}
i
}
}
return positions
}方法二：滑动窗口
因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
在算法的实现中，我们可以使用数组来存储字符串 p 和滑动窗口中每种字母的数量。
当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。
复杂度分析： O(m (n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m 1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ)。因为 s 和 p 仅包含小写字母，所以 Σ=26。
空间复杂度： O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。
代码语言：javascript复制func findAnagrams(s string, p string) []int {
if len(s) < len(p) {
return nil
}
var sCount, pCount [26]int
// 初始化字符串 p 中每种字母的数量。
// 初始化滑动窗口中每种字母的数量。
for i := 0; i < len(p); i {
sCount[s[i]-'a']
pCount[p[i]-'a']
}
var r []int
for i := 0; i <= len(s) - len(p); i {
if sCount == pCount {
r = append(r, i)
}
// 向右移动滑动窗口，移动一个字母。
sCount[s[i]-'a']--
if i len(p) < len(s) {
sCount[s[i len(p)]-'a']
}
}
return r
}参考文献
438. 找到字符串中所有字母异位词
