给定两个字符串 s 和 p,找到 s 中所有 p 的「异位词」的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
Medium。
★★★★☆
出题公司:阿里、腾讯、字节。
容易想到的解法是遍历字符串的所有字符,判断每个字符为起点、长度为 len§ 的子串是否是异位词。
如何判断是否是异位词呢?
异位词指由相同字母重排列形成的字符串(包括相同的字符串)。
通过定义,我们可以知道如果构成字符串的字母相同,且每个字母出现的次数相同,则为异位词。
关于数据结构的选择,可以使用 map 存储字母及其出现的个数。
时间复杂度: 这种解法的空间复杂度很高 O(len(s)*len(p))
。
空间复杂度: O(len(p))
。
注意:这种解法可以通过测试用例,但会超时。
下面以 Golang 为给出实现。
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 和滑动窗口中每种字母的数量。
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
}