以下是 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 语言,将上述代码粘贴到函数模板中即可。注意函数名和参数名需与题目要求一致。

 

更多推荐