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

Leecode刷题C语言之统计重新排列后包含另一个字符串的子字符串数目②

news 2025/6/23 18:09:29

执行结果:通过

执行用时和内存消耗如下：

void update(int *diff, int c, int add, int *cnt) {diff[c] += add;if (add == 1 && diff[c] == 0) {// 表明 diff[c] 由 -1 变为 0(*cnt)--;} else if (add == -1 && diff[c] == -1) {// 表明 diff[c] 由 0 变为 -1(*cnt)++;}
}long long validSubstringCount(char* word1, char* word2) {int diff[26] = {0};for (const char *c = word2; *c; c++) {diff[*c - 'a']--;}int cnt = 0;for (int i = 0; i < 26; i++) {if (diff[i] < 0) {cnt++;}}long long res = 0;int l = 0, r = 0;int len1 = strlen(word1);while (l < len1) {while (r < len1 && cnt > 0) {update(diff, word1[r] - 'a', 1, &cnt);r++;}if (cnt == 0) {res += len1 - r + 1;}update(diff, word1[l] - 'a', -1, &cnt);l++;}return res;
}

解题思路：

这段代码的主要思路是为了解决一个特定的问题：给定两个字符串 word1 和 word2，计算 word1 中有多少个不同的子串可以通过将 word2 中的一些字符恰好替换为其他字符（不限制替换成什么字符）而得到。这里的关键在于理解 word2 中的字符可以被移除（通过替换为任意其他字符），但不能被添加。

以下是代码的详细思路：

初始化差异数组：
- 创建一个长度为 26 的数组 diff 来记录 word2 中每个字母相对于 word1 可能需要移除的数量。数组下标对应字母的 ASCII 码减去 'a' 的 ASCII 码，这样 diff[0] 对应 'a'，diff[25] 对应 'z'。
- 遍历 word2，对于每个字符，将其在 diff 数组中对应位置的计数减一，表示这个字符在 word2 中存在，但在转换过程中可能需要被移除。
计算初始负差异计数：
- 遍历 diff 数组，统计所有负值的数量，存储在变量 cnt 中。这个数量表示 word2 中相对于 word1 多余的字符数量，这些字符在转换过程中必须被移除。
使用滑动窗口在 word1 中寻找有效子串：
- 初始化左右指针 l 和 r，以及结果变量 res。
- 使用一个循环，左指针 l 从字符串开始遍历到结束。
- 在内层循环中，右指针 r 从当前 l 的位置开始向右移动，同时更新 diff 数组和 cnt，直到 cnt 为 0。这一步是通过 update 函数实现的，每次移动右指针时，将对应字符的差异加一（表示尝试将该字符包含在子串中），如果之前该字符的差异是 -1（表示需要从 word2 中移除该字符才能匹配），则这次加一操作会使差异变为 0，意味着该字符不再需要被移除，因此 cnt 减一。
- 当 cnt 为 0 时，表示当前窗口内的字符集合可以通过移除 word2 中的一些字符（不需要添加字符）来匹配，因此所有以当前左指针 l 开头的子串都是有效的。计算这些有效子串的数量并加到 res 上。
- 然后，左指针 l 向右移动一位，同时更新 diff 数组和 cnt，这次是将左指针指向的字符的差异减一（表示尝试将该字符从子串中移除），如果之前该字符的差异是 0（表示该字符在 word2 中没有对应字符需要移除，但现在因为左指针的移动，该字符变成了需要被移除的字符），则这次减一操作会使差异变为 -1，意味着需要移除的字符数量增加，因此 cnt 加一。
返回结果：
- 循环结束后，返回累计的有效子串数量 res。