找到字符串中的所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
codeType
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
codeType
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
- 1 <= s.length, p.length <= 3 * 104
- s 和 p 仅包含小写字母
解法
ts
function findAnagrams(s: string, p: string): number[] {
// 用滑动窗口解决，同时用哈希表判断窗口内子串是不是异位词
const map = new Map<string, number>()
const n = s.length
const m = p.length
if(n < m) return []
// 用哈希表记录每个单词的个数
for(let i = 0; i < m; i++){
if(map.has(p[i])){
map.set(p[i], map.get(p[i]) + 1)
}else{
map.set(p[i], 1)
}
}
let start = 0 // 窗口指针
const res = []
// 先处理初始窗口里的m个元素
for(let i = 0; i < m; i++){
if(map.has(s[i])){
map.set(s[i], map.get(s[i]) - 1)
}
}
while(start <= n - m){
// 判断当前窗口元素是否是p的异位词，map中所有元素都为0
let isRes = true
for(const value of map.values()){
if(value !== 0){
isRes = false
break
}
}
if(isRes){
res.push(start)
}
// 窗口后移
start++
// 元素出窗口
let outCh = s[start - 1]
if(map.has(outCh)){
map.set(outCh, map.get(outCh) + 1)
}
// 元素入窗口
let inCh = s[start + m - 1]
if(map.has(inCh)){
map.set(inCh, map.get(inCh) - 1)
}
}
return res
};
上面的解法中，窗口内元素是否是异位词的判断需要遍历map，存在冗余计算，可以优化。
通过比较元素目标个数是变零还是从零变成非零来维护达成目标的所需的元素个数matchTarget，只需要matchTarget === 0就说明窗口内是异位词。
ts
function findAnagrams(s: string, p: string): number[] {
// 用滑动窗口解决，同时用哈希表判断窗口内子串是不是异位词
const map = new Map<string, number>()
const n = s.length
const m = p.length
if(n < m) return []
// 用哈希表记录每个单词的个数
for(let i = 0; i < m; i++){
map.set(p[i], (map.get(p[i]) || 0) + 1)
}
let start = 0 // 窗口指针
let matchTarget = map.size // 达成目标元素所需个数
const res = []
// 先处理初始窗口里的m个元素
for(let i = 0; i < m; i++){
if(map.has(s[i])){
const preCount = map.get(s[i])
const curCount = preCount - 1
map.set(s[i], curCount)
if(curCount === 0){ // 元素归0
matchTarget--
}else if(preCount === 0){ // 元素从0变成非0
matchTarget++
}
}
}
while(start <= n - m){
// 判断当前窗口元素是否是p的异位词，matchTaget === 0
if(matchTarget === 0){
res.push(start)
}
// 窗口后移
start++
// 元素出窗口
let outCh = s[start - 1]
if(map.has(outCh)){
const preCount = map.get(outCh)
const curCount = preCount + 1
map.set(outCh, curCount)
if(curCount === 0){ // 元素归0
matchTarget--
}else if(preCount === 0){ // 元素从0变成非0
matchTarget++
}
}
// 元素入窗口
let inCh = s[start + m - 1]
if(map.has(inCh)){
const preCount = map.get(inCh)
const curCount = preCount - 1
map.set(inCh, curCount)
if(curCount === 0){ // 元素归0
matchTarget--
}else if(preCount === 0){ // 元素从0变成非0
matchTarget++
}
}
}
return res
};