跳到主要内容

字母异位词分组

· 阅读需 6 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——49题​

💡 参考代码：​

#define MAX_STR_SIZE 100

typedef struct {
    int len;
    int idx;
    char str[MAX_STR_SIZE + 1];
} sort_str_t;

int cmp1(const void *a, const void *b)
{
    char x = *(char *)a;
    char y = *(char *)b;
    return x - y;
}

int cmp2(const void *a, const void *b)
{
    sort_str_t *x = (sort_str_t *)a;
    sort_str_t *y = (sort_str_t *)b;
    int diff = strcmp(x->str, y->str);
    if (diff != 0) {
        return diff;
    }
    return x->idx - y->idx;
}

/**
 * 将字母异位词组合在一起
 * @param strs 输入的字符串数组
 * @param strsSize 字符串数组的长度
 * @param returnSize 返回结果的行数
 * @param returnColumnSizes 返回每行的列数
 * @return 分组后的字母异位词二维数组
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    // 处理边界情况
    if (strsSize == 0) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
    
    // 分配返回结果的内存空间
    char ***ret = (char ***)malloc(strsSize * sizeof(char **));
    *returnColumnSizes = (int *)malloc(strsSize * sizeof(int));
    sort_str_t *hash_array = (sort_str_t *)malloc(strsSize * sizeof(sort_str_t));

    // 初始化结构体数组：复制原字符串并排序
    for (int i = 0; i < strsSize; i++) {
        hash_array[i].len = strlen(strs[i]);
        hash_array[i].idx = i;
        strcpy(hash_array[i].str, strs[i]);
        // 对每个字符串的字符进行排序
        qsort(hash_array[i].str, hash_array[i].len, sizeof(char), cmp1);
    }
    
    // 对结构体数组按排序后的字符串进行排序
    qsort(hash_array, strsSize, sizeof(sort_str_t), cmp2);
    
    // 按排序后的结果进行分组
    int ret_size = 0;
    int j = 0;
    while (j < strsSize) {
        int k = j + 1;
        // 找到所有具有相同排序字符串的元素
        while (k < strsSize && !strcmp(hash_array[j].str, hash_array[k].str)) {
            k++;
        }
        
        // 计算当前分组的大小
        int group_size = k - j;
        (*returnColumnSizes)[ret_size] = group_size;
        
        // 为当前分组分配内存
        ret[ret_size] = (char **)malloc(group_size * sizeof(char *));
        
        // 填充当前分组的数据
        for (int i = 0; i < group_size; i++) {
            ret[ret_size][i] = (char *)malloc((hash_array[j].len + 1) * sizeof(char));
            strcpy(ret[ret_size][i], strs[hash_array[i + j].idx]);
        }
        
        ret_size++;
        j += group_size;
    }
    
    *returnSize = ret_size;
    // 释放临时内存
    free(hash_array);
    
    return ret;
}

📖 总结：​

点击展开题目总结

🤔 字母异位词分组

1️⃣ 题目核心信息​

🎯 功能描述：将字符串数组中互为字母异位词的字符串归为一组

📥 输入输出：

  • 输入：
    • strs: 字符串数组
    • strsSize: 字符串数组长度
  • 输出：
    • 返回分组后的二维字符串数组
    • returnSize: 返回结果行数
    • returnColumnSizes: 返回每行列数的数组

2️⃣ 实现原理​

💡 核心思路：利用字母异位词排序后相同的特性，通过排序和分组实现归类

📋 实现步骤：

  1. 对每个字符串内部字符进行排序，生成统一的键值
  2. 将所有排序后的字符串与原始索引一起保存
  3. 对这些结构体按排序后的字符串进行排序
  4. 遍历排序后的数组，将相同键值的字符串归为一组

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用结构体保存原始索引和排序后的字符串，便于后续分组
  • 两次排序：先对字符串内部排序，再对整个数组排序
  • 线性扫描分组：排序后相同元素必然相邻，只需遍历分组

4️⃣ 使用场景​

✅ 适用情况：​

  • 需要对具有相同元素但顺序不同的数据进行分组
  • 字符串处理和分类问题
  • 数据去重和归类操作

⚠️ 前提条件：​

  • 输入字符串只包含小写字母
  • 需要保持相同字母异位词在同一组

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(N * M * log M + N * log N)

    • N为字符串数量，M为字符串平均长度
    • 每个字符串内部排序：O(M * log M)
    • 结构体数组排序：O(N * log N)

  • 💾 空间复杂度：O(N * M)

    • N为字符串数量，M为字符串平均长度
    • 需要额外空间存储结构体数组和结果数组

6️⃣ 注意事项​

🚩 边界情况：​

  • 空字符串数组
  • 包含空字符串的数组
  • 只有一个字符串的数组

💥 易错点：​

  • 忘记保存原始索引导致无法获取原始字符串
  • 内存分配后未正确释放导致内存泄漏
  • 分组时边界条件处理错误

7️⃣ 补充说明​

以输入数组：["eat", "tea", "tan", "ate", "nat", "bat"]为例

执行步骤详解​

第一步：初始化结构体数组

创建 sort_str_t 结构体数组，对每个字符串进行内部排序：

索引0: "eat" -> 排序后 "aet"
索引1: "tea" -> 排序后 "aet"
索引2: "tan" -> 排序后 "ant"
索引3: "ate" -> 排序后 "aet"
索引4: "nat" -> 排序后 "ant"
索引5: "bat" -> 排序后 "abt"

此时 hash_array 内容：

hash_array[0]: {len=3, idx=0, str="aet"}
hash_array[1]: {len=3, idx=1, str="aet"}
hash_array[2]: {len=3, idx=2, str="ant"}
hash_array[3]: {len=3, idx=3, str="aet"}
hash_array[4]: {len=3, idx=4, str="ant"}
hash_array[5]: {len=3, idx=5, str="abt"}

第二步：对结构体数组排序 按照 str 字段进行排序（如果相同则按 idx 排序）：

排序后 hash_array 内容：

hash_array[0]: {len=3, idx=5, str="abt"}  // 对应 "bat"
hash_array[1]: {len=3, idx=2, str="ant"}  // 对应 "tan"
hash_array[2]: {len=3, idx=4, str="ant"}  // 对应 "nat"
hash_array[3]: {len=3, idx=0, str="aet"}  // 对应 "eat"
hash_array[4]: {len=3, idx=1, str="aet"}  // 对应 "tea"
hash_array[5]: {len=3, idx=3, str="aet"}  // 对应 "ate"

第三步：分组处理

分组处理过程​

遍历排序后的数组，将相同字符串的归为一组：

  1. 处理 "abt" 组：

    • 只有索引5（"bat"）
    • 创建第一组：["bat"]

  2. 处理 "ant" 组：

    • 索引2（"tan"）和索引4（"nat"）
    • 创建第二组：["tan", "nat"]

  3. 处理 "aet" 组：

    • 索引0（"eat"）、索引1（"tea"）和索引3（"ate"）
    • 创建第三组：["eat", "tea", "ate"]

最终结果​

返回结果：

[
  ["bat"],
  ["tan", "nat"],
  ["eat", "tea", "ate"]
]

这个算法通过排序将字母异位词转换为相同的形式，然后利用排序后数组中相同元素必然相邻的特性，实现了高效的分组操作。

加载评论中...