每日一题——字母异位词分组

1. 问题描述

字母异位词 是指通过重新排列源单词的所有字母得到的一个新单词。例如，“eat” 和 “tea” 是字母异位词。

题目要求：给定一个字符串数组，将字母异位词组合在一起，并以任意顺序返回结果列表。

示例

示例 1：

• 输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
• 输出：[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

示例 2：

• 输入：strs = [""]
• 输出：[[""]]

示例 3：

• 输入：strs = ["a"]
• 输出：[["a"]]

提示

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

2. 解题思路

解决这个问题的关键在于如何快速判断两个字符串是否是字母异位词。一种有效的方法是：

1. 排序法：将每个字符串排序后，字母异位词的排序结果相同。
2. 哈希表：使用哈希表存储排序后的字符串作为键，原始字符串作为值。

具体步骤

1. 排序字符串：对每个字符串进行排序，得到其“标准形式”。
2. 哈希表存储：将排序后的字符串作为键，原始字符串作为值存储到哈希表中。
3. 分组：根据哈希表的键将字符串分组。
4. 返回结果：将分组结果转换为所需的格式。

3. 代码实现

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

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

// 定义每组最多字符串数和每个字符串的最大长度
#define MAX_CNT 10000
#define MAX_LEN 101

// 比较函数，用于 qsort 对字符数组进行排序
int cmp(const void *a, const void *b) {
    char *aa = (char *)a;
    char *bb = (char *)b;
    return (*aa - *bb);  // 按字典序比较字符
}

// 哈希表结构体
typedef struct HashMap {
    char *key;  // 排序后的字符串作为键,用字符串作为键。
    char array[MAX_CNT][MAX_LEN];  // 存储属于同一组的原始字符串
    int num;  // 当前组的字符串数量
    UT_hash_handle hh;  // 哈希表句柄，用于管理哈希表
} HashMap;

HashMap *hashTable = NULL;  // 哈希表指针
int g_groupSize = 0;  // 分组数量

// 向哈希表中添加分组
void AddGroup(char *key, char *member) {
    HashMap *hashNode = NULL;
    HASH_FIND_STR(hashTable, key, hashNode);  // 在哈希表中查找键为 key 的节点
    if (hashNode == NULL) {
        // 如果键不存在，说明找到个新的字符串组，则创建新的哈希表节点
        hashNode = (HashMap *)calloc(1, sizeof(HashMap));
        hashNode->key = (char *)calloc(strlen(key) + 1, sizeof(char));  // 分配内存存储键
        strcpy(hashNode->key, key);  // 复制键值
        hashNode->num = 1;  // 初始化当前组的字符串数量为 1
        strcpy(hashNode->array[0], member);  // 将第一个字符串存储到数组中
        HASH_ADD_STR(hashTable, key, hashNode);  // 将新节点添加到哈希表中
        g_groupSize++;  // 分组数量加 1
    } else {
        // 如果键已存在，则将新字符串添加到当前组中
        strcpy(hashNode->array[hashNode->num], member);  // 复制字符串到数组
        hashNode->num += 1;  // 当前组的字符串数量加 1
    }
}

// 释放哈希表内存
void FreeHashTable() {
    HashMap *hashNode, *tempNode;
    HASH_ITER(hh, hashTable, hashNode, tempNode) {  // 遍历哈希表
        free(hashNode->key);  // 释放键的内存
        HASH_DEL(hashTable, hashNode);  // 从哈希表中删除节点
    }
}

// 主函数：分组字母异位词
char ***groupAnagrams(char **strs, int strsSize, int *returnSize, int **returnColumnSizes) {
    hashTable = NULL;  // 初始化哈希表为空
    g_groupSize = 0;  // 初始化分组数量为 0

    // 遍历字符串数组，实现分组
    for (int i = 0; i < strsSize; i++) {
        char *curStr = strs[i];  // 当前处理的字符串
        char *sortStr = (char *)calloc(strlen(curStr) + 1, sizeof(char));  // 分配内存存储排序后的字符串
        strcpy(sortStr, curStr);  // 复制当前字符串到 sortStr
        qsort(sortStr, strlen(sortStr), sizeof(char), cmp);  // 对 sortStr 进行排序
        AddGroup(sortStr, curStr);  // 将排序后的字符串作为键，将当前字符串归类到对应的分组中
        free(sortStr);  // 释放 sortStr 的内存
    }

    // 分组后填写结果
    *returnSize = g_groupSize;  // 设置返回的分组数量
    *returnColumnSizes = (int *)calloc(g_groupSize, sizeof(int));  // 分配返回的列大小数组
    char ***ret = (char ***)calloc(g_groupSize, sizeof(char **));  // 分配返回的二维数组

    int index = 0;  // 用于记录当前处理的分组索引
    HashMap *cur, *temp;
    HASH_ITER(hh, hashTable, cur, temp) {  // 遍历哈希表
        (*returnColumnSizes)[index] = cur->num;  // 设置当前分组的列大小
        ret[index] = (char **)calloc(cur->num, sizeof(char *));  // 分配当前分组的二维数组
        for (int i = 0; i < cur->num; i++) {
            ret[index][i] = (char *)calloc(strlen(cur->key) + 1, sizeof(char));  // 分配每个字符串的内存
            strcpy(ret[index][i], cur->array[i]);  // 复制字符串到结果数组中
        }
        index++;  // 处理下一个分组
    }

    FreeHashTable();  // 释放哈希表内存
    return ret;  // 返回结果
}

// 测试函数
int main() {
    char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};  // 输入字符串数组
    int strsSize = sizeof(strs) / sizeof(strs[0]);  // 字符串数组的大小
    int returnSize = 0;  // 返回的分组数量
    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");  // 换行
    }

    return 0;  // 程序结束
}
// 作者：yeyeLatte
// 链接：https://leetcode.cn/problems/group-anagrams/solutions/2979357/zi-mu-yi-wei-ci-fen-zu-cyu-yan-utha-xi-b-1i0m/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

4. 代码解析

（1）排序法

通过将字符串排序，将字母异位词转换为相同的“标准形式”。例如：

• "eat" 排序后为 "aet"。
• "tea" 排序后也为 "aet"。

（2）哈希表存储

使用UT_hash库管理哈希表，以排序后的字符串作为键，原始字符串作为值存储。这样可以快速查找和分组字母异位词。

（3）动态内存分配

为了支持任意长度的输入，代码中使用了动态内存分配：

• 每个分组的字符串存储在二维数组中。
• 分组数量和每个分组的大小动态分配。

（4）释放内存

在函数结束时，释放所有动态分配的内存，避免内存泄漏。
HASH_FIND_STR 是 UTHash 库中用于在哈希表中查找特定键的宏。UTHash 是一个轻量级的哈希表库，广泛用于 C 语言项目中，用于实现哈希表功能。

1. HASH_FIND_STR 的作用

HASH_FIND_STR 用于在哈希表中查找是否存在某个键（key），并返回对应的哈希表节点（hashNode）。如果找到匹配的键，则将节点的指针存储到 hashNode 中；如果没有找到，则 hashNode 为 NULL。

2. 宏的定义

HASH_FIND_STR(head, findstr, out)

• head：指向哈希表的头指针（通常是全局变量或局部变量）。
• findstr：要查找的键（key），类型为 const char*。
• out：输出参数，用于存储找到的哈希表节点的指针。如果未找到，则为 NULL。

4. 详细解释

（1）head 参数

head 是指向哈希表头的指针。在 UTHash 中，哈希表的头指针用于管理整个哈希表。例如：

HashNode *hashTable = NULL;  // 初始化为空

（2）findstr 参数

findstr 是要查找的键，类型为 const char*。例如：

const char *key = "exampleKey";
HASH_FIND_STR(hashTable, key, hashNode);

（3）out 参数

out 是输出参数，用于存储找到的哈希表节点的指针。如果找到匹配的键，则 out 指向对应的节点；否则，out 为 NULL。例如：

5. 总结

本题的关键在于如何快速判断两个字符串是否是字母异位词。通过排序法和哈希表，可以高效地实现分组功能。这种方法的时间复杂度为O(n * k * log k)，其中n是字符串数量，k是字符串的最大长度。
这题确实挺难的，反正让我写肯定写不出来，尤其是C语言的。建议先写C++版本的，容易理解很多，先理解整体思路。要知道这个整体上只是用一个字符串当作一个键，用一个字符串数组代替值。相当于上升一个维度。难度提升很大。