C语言刷题 LeetCode 30天挑战 (六)字母异位词分组-难
//Group Anagrams
//Given an array of strings, group anagrams together.
// Input :ltea""tan""ate","nat","bat"],
// Output:
// [
// ["ate" ,"eat","tea"],
// ["nat","tan"],
// ["bat"]
// ]
// Note:
// All inputs will be in lowercase.
// The order of your output does not matter
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 用于比较两个字符的排序函数
int cmp(const void *a, const void *b) {
return *(char *)a - *(char *)b;
}
// 哈希表的结构,保存排序后的键和原始字符串数组
typedef struct {
char *sortedStr;
char **anagrams;
int count;
int capacity;
} HashEntry;
// 动态数组的初始化大小
#define INITIAL_CAPACITY 10
// 查找或插入哈希表条目
int findOrInsert(HashEntry *hashTable, int *tableSize, char *sortedStr) {
for (int i = 0; i < *tableSize; ++i) {
if (strcmp(hashTable[i].sortedStr, sortedStr) == 0) {
return i;
}
}
hashTable[*tableSize].sortedStr = strdup(sortedStr);
hashTable[*tableSize].anagrams = (char **)malloc(INITIAL_CAPACITY * sizeof(char *));
hashTable[*tableSize].count = 0;
hashTable[*tableSize].capacity = INITIAL_CAPACITY;
return (*tableSize)++;
}
// 主函数,用于分组字母异位词
char ***groupAnagrams(char **strs, int strsSize, int *returnSize, int **returnColumnSizes) {
if (strsSize == 0) {
*returnSize = 0;
*returnColumnSizes = NULL;
return NULL;
}
// 初始化哈希表
HashEntry *hashTable = (HashEntry *)malloc(strsSize * sizeof(HashEntry));
int tableSize = 0;
// 遍历每个字符串
for (int i = 0; i < strsSize; ++i) {
char *str = strs[i];
int len = strlen(str);
// 排序每个字符串的字符
char *sortedStr = strdup(str);
qsort(sortedStr, len, sizeof(char), cmp);
// 查找或插入哈希表条目
int idx = findOrInsert(hashTable, &tableSize, sortedStr);
// 将原始字符串加入到对应的分组中
if (hashTable[idx].count == hashTable[idx].capacity) {
hashTable[idx].capacity *= 2;
hashTable[idx].anagrams = (char **)realloc(hashTable[idx].anagrams, hashTable[idx].capacity * sizeof(char *));
}
hashTable[idx].anagrams[hashTable[idx].count++] = strdup(str);
free(sortedStr); // 释放排序后的字符串
}
// 分配结果数组
char ***result = (char ***)malloc(tableSize * sizeof(char **));
*returnColumnSizes = (int *)malloc(tableSize * sizeof(int));
*returnSize = tableSize;
// 填充结果
for (int i = 0; i < tableSize; ++i) {
result[i] = (char **)malloc(hashTable[i].count * sizeof(char *));
(*returnColumnSizes)[i] = hashTable[i].count;
for (int j = 0; j < hashTable[i].count; ++j) {
result[i][j] = hashTable[i].anagrams[j];
}
free(hashTable[i].sortedStr);
free(hashTable[i].anagrams); // 不需要的指针数组释放
}
free(hashTable); // 释放哈希表
return result;
}
int main() {
// 输入字符串数组
char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
int strsSize = sizeof(strs) / sizeof(strs[0]);
// 定义返回变量
int returnSize;
int *returnColumnSizes;
// 调用分组函数
char ***result = groupAnagrams(strs, strsSize, &returnSize, &returnColumnSizes);
// 打印结果
printf("[\n");
for (int i = 0; i < returnSize; i++) {
printf(" [");
for (int j = 0; j < returnColumnSizes[i]; j++) {
printf("\"%s\"", result[i][j]);
if (j < returnColumnSizes[i] - 1) {
printf(", ");
}
}
printf("]");
if (i < returnSize - 1) {
printf(",\n");
}
}
printf("\n]\n");
// 释放内存
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < returnColumnSizes[i]; j++) {
free(result[i][j]);
}
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}
排序字符:使用 qsort 对每个字符串的字符进行排序,将异位词变成相同的键。
哈希表存储:每个排序后的字符串作为键,原始字符串作为值存入哈希表中。哈希表用来分组异位词。
结果构建:在最终输出时,将每个分组的字符串数组放入结果数组。
内存管理:动态分配内存,确保所有字符串、分组和结果数组被正确分配和释放。
原文地址:https://blog.csdn.net/weixin_64593595/article/details/142673887
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!