题目
给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
代码
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义一个结构体来存储字符串及其相关信息
typedef struct {
char* str; // 排序后的字符串
char* oldstr; // 原始字符串
int len; // 字符串长度
int isGrouped; // 是否已分组
int indexInRes; // 在结果数组中的索引
} str_t;
// 用于根据字符串长度排序的比较函数
int cmp1(const void* a, const void* b) {
return ((str_t*)a)->len - ((str_t*)b)->len;
}
// 用于对字符串中的字符排序的比较函数
int cmp2(const void* a, const void* b) {
return (*(char*)a) - (*(char*)b);
}
// 主函数,用于分组字母异位词
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
str_t str_st[10000] = {0}; // 存储字符串及其信息的结构体数组
char ***res = (char***)malloc(sizeof(char**) * strsSize); // 结果数组
*returnColumnSizes = (int*)malloc(sizeof(int) * strsSize); // 每个组的大小数组
*returnSize = 0; // 初始组数为0
// 初始化结果数组和列大小数组
for (int i = 0; i < strsSize; i++) {
res[i] = (char**)malloc(sizeof(char*) * strsSize);
(*returnColumnSizes)[i] = 0;
}
// 处理输入字符串,将其排序并存储在结构体数组中
for (int i = 0; i < strsSize; i++) {
str_st[i].oldstr = strs[i];
str_st[i].len = strlen(strs[i]);
str_st[i].str = strdup(strs[i]);
qsort(str_st[i].str, str_st[i].len, sizeof(char), cmp2);
}
// 根据字符串长度对结构体数组进行排序
qsort(str_st, strsSize, sizeof(str_t), cmp1);
// 分组字母异位词
for (int i = 0; i < strsSize; i++) {
if (!str_st[i].isGrouped) { // 如果当前字符串没有被分组
str_st[i].indexInRes = *returnSize;
res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[i].oldstr;
str_st[i].isGrouped = 1;
for (int j = i + 1; j < strsSize; j++) {
if (strcmp(str_st[i].str, str_st[j].str) == 0) {
res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[j].oldstr;
str_st[j].isGrouped = 1;
}
}
(*returnSize)++;
}
}
return res;
}
// 主函数测试
int main() {
char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
int strsSize = 6;
int returnSize;
int *returnColumnSizes;
char ***result = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("%s ", result[i][j]);
}
printf("\n");
}
// 释放内存
for (int i = 0; i < returnSize; i++) {
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}
思路分析
题目要求将字母异位词组合在一起。字母异位词是指由相同字母组成但顺序不同的字符串。我们可以通过对每个字符串进行排序,使其相同字母的字符串能够变得相等。然后根据排序后的字符串进行分组。
(写完才发现好像不用排序len,,,反正都要遍历,然后看isgrouped…
拆解分析
-
结构体定义:
str_t
结构体用于存储原始字符串、排序后的字符串、长度、是否已分组标志以及在结果数组中的索引。
-
比较函数:
cmp1
:用于根据长度排序。cmp2
:用于字符串排序。
-
内存分配:
- 动态分配结果数组
res
和每个组大小的数组returnColumnSizes
。
- 动态分配结果数组
-
字符串处理和排序:
- 对每个字符串进行排序,并按长度排序
str_st
数组。
- 对每个字符串进行排序,并按长度排序
-
分组逻辑:
- 遍历字符串数组,根据排序后的字符串相等性进行分组,并更新
returnSize
和returnColumnSizes
。
- 遍历字符串数组,根据排序后的字符串相等性进行分组,并更新
详细拆解
-
初始化数据结构:
str_t str_st[10000] = {0}; // 存储字符串及其信息的结构体数组 char ***res = (char***)malloc(sizeof(char**) * strsSize); // 结果数组 *returnColumnSizes = (int*)malloc(sizeof(int) * strsSize); // 每个组的大小数组 *returnSize = 0; // 初始组数为0
-
为每个组初始化结果数组和列大小数组:
for (int i = 0; i < strsSize; i++) { res[i] = (char**)malloc(sizeof(char*) * strsSize); (*returnColumnSizes)[i] = 0; }
-
处理输入字符串,将其排序并存储在结构体数组中:
for (int i = 0; i < strsSize; i++) { str_st[i].oldstr = strs[i]; str_st[i].len = strlen(strs[i]); str_st[i].str = strdup(strs[i]); qsort(str_st[i].str, str_st[i].len, sizeof(char), cmp2); }
-
根据字符串长度对结构体数组进行排序:
qsort(str_st, strsSize, sizeof(str_t), cmp1);
-
分组字母异位词:
for (int i = 0; i < strsSize; i++) { if (!str_st[i].isGrouped) { // 如果当前字符串没有被分组 str_st[i].indexInRes = *returnSize; res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[i].oldstr; str_st[i].isGrouped = 1; for (int j = i + 1; j < strsSize; j++) { if (strcmp(str_st[i].str, str_st[j].str) == 0) { res[*returnSize][(*returnColumnSizes)[*returnSize]++] = str_st[j].oldstr; str_st[j].isGrouped = 1; } } (*returnSize)++; } }
-
主函数测试:
int main() { char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"}; int strsSize = 6; int returnSize; int *returnColumnSizes; char ***result = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes); for (int i = 0; i < returnSize; i++) { for (int j = 0; j < returnColumnSizes[i]; j++) { printf("%s ", result[i][j]); } printf("\n"); } // 释放内存 for (int i = 0; i < returnSize; i++) { free(result[i]); } free(result); free(returnColumnSizes); return 0; }
复杂度分析
-
时间复杂度:
- 对每个字符串排序的时间复杂度为
O(N log N)
,其中 N 为字符串长度。 - 对结构体数组进行排序的时间复杂度为
O(M log M)
,其中 M 为字符串数组的大小。 - 总时间复杂度为
O(M * N log N)
,M 是字符串数组的大小,N 是最长字符串的长度。
- 对每个字符串排序的时间复杂度为
-
空间复杂度:
- 主要由存储结果的二维数组
res
和辅助数组str_st
组成。总体空间复杂度为 O(M * N)。
- 主要由存储结果的二维数组