当前位置：首页 > article >正文

【LeetCode】每日一题 2024_1_10 统计重新排列后包含另一个字符串的子字符串数目 II（滑动窗口）

article 2025/1/11 13:09:29

前言

每天和你一起刷 LeetCode 每日一题~

拼尽全力无法战胜期末考试

寒假 . . . 堂堂复活！

每日一题重出江湖！

就用我最擅长的滑动窗口类型的每日一题作为我寒假回归的第一题！

LeetCode 启动！

题目：统计重新排列后包含另一个字符串的子字符串数目 II

代码与解题思路

先读题：用 word2 作为 word1 子串重排之后的前缀就算作一个合法字符串，问总共有多少个合法字符串

对于这个题目，我们需要理解的核心问题就是：

判断字符串是否合法，因为 word1 字符串可以重排，所以判断 word2 是否能成为 word1 的前缀，就需要对每个字符进行计数并判断 word1 子串字符的计数是否大于等于 word2 子串的数量

代码及详细注释如下：

func validSubstringCount(word1 string, word2 string) (ans int64) {
    // 经典子数组型滑窗
    // word2 作为 word1 的前缀，将他的字符计数需要在 word1 子串中全部出现
    need := [26]int{} 
    // 记录 word1 子串出现的字符
    cnt := [26]int{}
    // 用于判断 word2 和 word1 字符计数相同
    //（不能用 map 判断，因为会出现 word1 字符比 word2 多但是符合条件的情况）
    // 字符的种类
    typeCnt := 0
    for _, v := range word2 {
        idx := int(v-'a')
        if need[idx] == 0 { // 字符种类++
            typeCnt++
        }
        need[idx]++
    }

    // 滑窗
    l := 0
    for r, v := range word1 {
        idx := int(v-'a')
        cnt[idx]++
        // word1 当前字符数量 >= word2 时，word2 都能作为 word1 的前缀
        if cnt[idx] == need[idx] {
            typeCnt--
        }
        // 当 word2 中字符都在 word1 子串出现了，证明可以作为他的前缀了
        for typeCnt == 0 {
            // 枚举左边界
            // 即当前子串已经符合要求，右边界无论加多少字符依然符合，所以直接把右边界都加上
            ans += int64(len(word1)-r) 
            ldx := int(word1[l]-'a') // 左边界出窗口
            cnt[ldx]--
            // word1 当前字符数量 < word2，word2 不能作为 word1 的前缀
            if cnt[ldx] < need[ldx] {
                typeCnt++
            }
            l++
        }
    }
    return ans
}