Kimi LeetCode 3298. 统计重新排列后包含另一个字符串的子字符串数目 II TypeScript实现
以下是 LeetCode 3298 的 TypeScript 实现,使用滑动窗口算法:
```typescript
function validSubstringCount(word1: string, word2: string): number {
if (word1.length < word2.length) {
return 0;
}
// 统计 word2 中每个字符的需求量
const need: number[] = new Array(26).fill(0);
let required = 0; // 还需要满足的字符种类数
for (const c of word2) {
if (need[c.charCodeAt(0) - 97]++ === 0) {
required++;
}
}
const cur: number[] = new Array(26).fill(0); // 当前窗口中各字符的数量
let res = 0;
let l = 0;
for (let r = 0; r < word1.length; r++) {
const rc = word1.charCodeAt(r) - 97;
if (++cur[rc] === need[rc]) {
required--; // 该字符需求已满足
}
// 当窗口满足所有字符需求时,收缩左边界
while (required === 0) {
const lc = word1.charCodeAt(l) - 97;
if (cur[lc] === need[lc]) {
required++; // 移出后将不再满足
}
cur[lc]--;
l++;
}
// 以 r 结尾的合法子串数量 = l(左边界可以取 0 ~ l-1)
res += l;
}
return res;
}
```
关键点
要点 说明
`charCodeAt(0) - 97` TypeScript 中用 `97` 替代 Java 的 `'a'.charCodeAt(0)`,获取字符在字母表中的索引
`number` 类型 TypeScript 中返回类型为 `number`,注意大数场景下可能需要用 `bigint`,但本题 `res` 在 `number` 安全范围内
滑动窗口 与 Java 解法完全一致,O(n) 时间,O(1) 空间
提交方式
在 LeetCode 上直接选择 TypeScript 语言,将上述代码粘贴到函数模板中即可。注意函数名和参数名需与题目要求一致。

更多推荐


所有评论(0)