Skip to main content

438. Find All Anagrams in a String

分析

经典滑动窗口,不过状态的利用和状态维护代码细节比较多
抽象了一层来专门做细节处理

题解

class CharRecord {
memo = new Map<string, number>()
need = new Map<string, number>()

constructor(needStr: string) {
needStr.split("").forEach((v) => {
const temp = this.need.get(v)
if (temp === undefined) {
this.need.set(v, 1)
return
}
this.need.set(v, temp + 1)
})
}

recordNewChar(newChar: string) {
const temp = this.memo.get(newChar)
if (temp === undefined) {
this.memo.set(newChar, 1)
return
}
this.memo.set(newChar, temp + 1)
}

deleteOldChar(deleteChar: string) {
// 从使用方来看被删除的代码一定是存在于 memo 的,但这里防御性提示下
const temp = this.memo.get(deleteChar)
if (temp === undefined) {
console.log("删除的元素并不存在")
return
}
const deleteCharCnt = temp
if (deleteCharCnt === 1) {
this.memo.delete(deleteChar)
return
}
this.memo.set(deleteChar, deleteCharCnt - 1)
}

get isEqualOrLargeNeeds() {
if (this.memo.size < this.need.size) {
return false
}
for (const [key, value] of this.need) {
const res = (this.memo.get(key) || 0) >= value
if (!res) {
return false
}
}
return true
}

get isEqualNeeds() {
if (this.memo.size !== this.need.size) {
return false
}
for (const [key, value] of this.need) {
const res = (this.memo.get(key) || 0) === value
if (!res) {
return false
}
}
return true
}
}

function findAnagrams(s: string, p: string): number[] {
const window = new CharRecord(p)
let lIndx = 0, rIndex = 0

const ans = []
while (rIndex < s.length) {
const newChar = s[rIndex]
rIndex++
window.recordNewChar(newChar)

while (lIndx <= rIndex && window.isEqualOrLargeNeeds) {
if (window.isEqualNeeds) {
ans.push(lIndx)
}
const deleteChar = s[lIndx]
lIndx++
window.deleteOldChar(deleteChar)
}
}
return ans
};