438. 找到字符串中所有字母异位词

题目

给定两个字符串 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" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写字母

代码

完整代码

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* findAnagrams(char * s, char * p, int* returnSize) {int len_s = strlen(s);int len_p = strlen(p);int* result = (int*)malloc(len_s * sizeof(int));*returnSize = 0;if (len_s < len_p) {return result;}int hash_p[26] = {0};int hash_s[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;hash_s[s[i] - 'a']++;}for (int i = 0; i <= len_s - len_p; i++) {if (memcmp(hash_p, hash_s, 26 * sizeof(int)) == 0) {result[(*returnSize)++] = i;}if (i + len_p < len_s) {hash_s[s[i] - 'a']--;hash_s[s[i + len_p] - 'a']++;}}return result;
}

思路分析

1. 使用滑动窗口在字符串 s 上检查长度为 len_p 的子串是否是 p 的异位词。
2. 使用两个哈希表分别记录 p 和当前窗口内的字符频率。
3. 滑动窗口每次移动时更新窗口内字符的频率，并与 p 的频率进行比较。

拆解分析

初始化哈希表

首先，我们需要记录 p 中每个字符的频率，同时记录 s 中前 len_p 个字符的频率。

int hash_p[26] = {0};
int hash_s[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;hash_s[s[i] - 'a']++;
}

滑动窗口检查

通过比较两个哈希表来判断当前窗口是否是 p 的异位词。如果是，则将当前窗口的起始索引加入结果。

for (int i = 0; i <= len_s - len_p; i++) {if (memcmp(hash_p, hash_s, 26 * sizeof(int)) == 0) {result[(*returnSize)++] = i;}if (i + len_p < len_s) {hash_s[s[i] - 'a']--;hash_s[s[i + len_p] - 'a']++;}
}

窗口移动

每次移动窗口时，更新窗口的字符频率，然后继续比较。

if (i + len_p < len_s) {hash_s[s[i] - 'a']--;hash_s[s[i + len_p] - 'a']++;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。初始化哈希表和滑动窗口移动都只需要遍历 s 一次。
• 空间复杂度：O(1)，只需要两个固定大小的哈希表来记录字符频率。

结果

一题多解

双指针法

双指针法思路分析

使用双指针来维护一个滑动窗口，其中一个指针表示窗口的起始位置，另一个指针表示窗口的结束位置。通过计数器来记录当前窗口内的字符频率。

具体步骤：

1. 初始化两个指针 left 和 right，以及一个计数器 count。
2. 移动 right 指针扩展窗口，并更新计数器。
3. 如果窗口大小等于 p 的长度，则检查是否是异位词。
4. 如果窗口大小超过 p 的长度，则移动 left 指针收缩窗口，并更新计数器。

双指针法复杂度分析

• 时间复杂度：O(n)，每个字符最多被访问两次（一次通过 right 指针，一次通过 left 指针）。
• 空间复杂度：O(1)，只需要固定大小的哈希表和计数器。

完整代码

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* findAnagrams(char * s, char * p, int* returnSize) {int len_s = strlen(s);int len_p = strlen(p);int* result = (int*)malloc(len_s * sizeof(int));*returnSize = 0;if (len_s < len_p) {return result;}int hash_p[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;}int left = 0, right = 0, count = len_p;while (right < len_s) {if (hash_p[s[right++] - 'a']-- > 0) {count--;}if (count == 0) {result[(*returnSize)++] = left;}if (right - left == len_p && hash_p[s[left++] - 'a']++ >= 0) {count++;}}return result;
}

拆解分析

初始化哈希表

记录 p 中每个字符的频率。

int hash_p[26] = {0};for (int i = 0; i < len_p; i++) {hash_p[p[i] - 'a']++;
}

移动右指针

移动 right 指针扩展窗口，并更新计数器。

int left = 0, right = 0, count = len_p;while (right < len_s) {if (hash_p[s[right++] - 'a']-- > 0) {count--;}

检查窗口

如果窗口大小等于 p 的长度，则检查是否是异位词。

if (count == 0) {result[(*returnSize)++] = left;
}

移动左指针

如果窗口大小超过 p 的长度，则移动 left 指针收缩窗口，并更新计数器。

if (right - left == len_p && hash_p[s[left++] - 'a']++ >= 0) {count++;
}

复杂度分析

• 时间复杂度：O(n)，每个字符最多被访问两次。
• 空间复杂度：O(1)，只需要固定大小的哈希表和计数器。

结果