每日一题——找到字符串中所有字母异位词

问题描述

给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，并返回这些子串的起始索引。不考虑答案输出的顺序。

示例

示例 1

• 输入: s = "cbaebabacd", p = "abc"
• 输出: [0, 6]
• 解释:
  • 起始索引等于 0 的子串是 “cba”，它是 “abc” 的字母异位词。
  • 起始索引等于 6 的子串是 “bac”，它是 “abc” 的字母异位词。

示例 2

• 输入: s = "abab", p = "ab"
• 输出: [0, 1, 2]
• 解释:
  • 起始索引等于 0 的子串是 “ab”，它是 “ab” 的字母异位词。
  • 起始索引等于 1 的子串是 “ba”，它是 “ab” 的字母异位词。
  • 起始索引等于 2 的子串是 “ab”，它是 “ab” 的字母异位词。

问题分析

本题的核心是通过滑动窗口的方式在字符串 s 中查找所有与字符串 p 的字母异位词匹配的子串。字母异位词是指字符种类和数量相同，但顺序可以不同的字符串。

解题思路

1. 滑动窗口：使用滑动窗口来遍历字符串 s，窗口大小固定为 p 的长度。
2. 字符频率统计：使用一个大小为 26 的整型数组 cnt 来统计字符频率，cnt[ch - 'a'] 表示字符 ch 的频率。
3. 差异计数：通过一个变量 diff 来记录当前窗口与目标字符串 p 的差异。当 diff 为 0 时，表示当前窗口是一个有效的字母异位词。
4. 结果存储：将所有满足条件的子串起始索引存储到结果数组中。

代码实现

以下是完整的 C 语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 找到字符串 s 中所有 p 的字母异位词的子串，并返回这些子串的起始索引。
 * @param s 输入字符串 s
 * @param p 输入字符串 p
 * @param returnSize 返回结果数组的大小
 * @return 返回结果数组
 */
int* findAnagrams(char* s, char* p, int* returnSize) {
    int m = strlen(s); // s 的长度
    int n = strlen(p); // p 的长度
    if (m < n) { // 如果 s 的长度小于 p 的长度，直接返回空数组
        *returnSize = 0;
        return NULL;
    }

    // 分配字符频率数组
    int* cnt = (int*)calloc(26, sizeof(int));
    int diff = n; // 初始差异为 p 的长度

    // 统计 p 中每个字符的频率
    for (int i = 0; i < n; i++) {
        cnt[p[i] - 'a']++;
    }

    // 分配结果数组
    *returnSize = 0;
    int* result = (int*)malloc(sizeof(int) * (m - n + 1));

    // 滑动窗口遍历 s
    for (int i = 0; i < m; ++i) {
        // 当前字符进入窗口
        diff += (cnt[s[i] - 'a'] > 0) ? -1 : 1; // 如果当前字符在 p 中出现过，diff 减 1，否则加 1
        --cnt[s[i] - 'a']; // 更新字符频率

        // 如果窗口大小超过 n，移除窗口左侧的字符
        if (i >= n) {
            diff += (cnt[s[i - n] - 'a'] < 0) ? -1 : 1; // 如果移除的字符在 p 中出现过，diff 加 1，否则减 1
            ++cnt[s[i - n] - 'a']; // 更新字符频率
        }

        // 如果 diff 为 0，说明当前窗口是一个有效的字母异位词
        if (diff == 0 && i >= n - 1) {
            result[(*returnSize)++] = i - n + 1; // 将窗口左端点加入结果数组
        }
    }

    // 释放字符频率数组
    free(cnt);
    return result;
}

代码说明

1. 字符频率数组：

   • 使用 int cnt[26] 来统计字符频率，cnt[ch - 'a'] 表示字符 ch 的频率。
   • 初始化时，遍历字符串 p，将每个字符的频率加 1。

2. 滑动窗口：

   • 使用一个滑动窗口来维护长度为 n 的子串。
   • 每次将一个字符加入窗口时，更新 diff 和 cnt。
   • 如果窗口大小超过 n，移除窗口左侧的字符，并更新 diff 和 cnt。

3. 结果存储：

   • 分配一个足够大的数组 result 来存储结果，其大小为 m - n + 1，即可能的子串数量。
   • 每次找到一个有效的字母异位词时，将窗口左端点的索引加入 result。

4. 内存管理：

   • 使用 calloc 分配字符频率数组，并在函数结束时释放。
   • 结果数组由调用者负责释放。

测试代码

以下是测试代码，用于验证函数的正确性：

#include <stdio.h>

int main() {
    char s[] = "cbaebabacd";
    char p[] = "abc";
    int returnSize = 0;
    int* result = findAnagrams(s, p, &returnSize);

    printf("Result: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result); // 释放分配的内存
    return 0;
}

输出

对于上述测试用例，输出应为：

Result: 0 6

这表示在字符串 s 中，从索引 0 和 6 开始的子串分别是 “cba” 和 “bac”，它们都是 “abc” 的字母异位词。

时间复杂度分析

• 时间复杂度：O(m)，其中 m 是字符串 s 的长度。滑动窗口遍历一次字符串 s，每次操作的时间复杂度为 O(1)。
• 空间复杂度：O(1)，除了输入和输出外，只使用了一个大小为 26 的数组来统计字符频率。

总结

这题确实很巧妙，理解滑动窗口的好题目。另外初始化为0，分配空间，要用calloc，而不是malloc。找了半天的bug。也算是长经验了。