49. 字母异位词分组

题目

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

思路分析

题目要求将字母异位词组合在一起。字母异位词是指由相同字母组成但顺序不同的字符串。我们可以通过对每个字符串进行排序，使其相同字母的字符串能够变得相等。然后根据排序后的字符串进行分组。
（写完才发现好像不用排序len，，，反正都要遍历，然后看isgrouped…

拆解分析

1. 结构体定义:

   • str_t结构体用于存储原始字符串、排序后的字符串、长度、是否已分组标志以及在结果数组中的索引。

2. 比较函数:

   • cmp1：用于根据长度排序。
   • cmp2：用于字符串排序。

3. 内存分配:

   • 动态分配结果数组 res 和每个组大小的数组 returnColumnSizes。

4. 字符串处理和排序:

   • 对每个字符串进行排序，并按长度排序 str_st 数组。

5. 分组逻辑:

   • 遍历字符串数组，根据排序后的字符串相等性进行分组，并更新 returnSize 和 returnColumnSizes。

详细拆解

1. 初始化数据结构:

   str_t str_st[10000] = {0};  // 存储字符串及其信息的结构体数组
   char ***res = (char***)malloc(sizeof(char**) * strsSize); // 结果数组
   *returnColumnSizes = (int*)malloc(sizeof(int) * strsSize); // 每个组的大小数组
   *returnSize = 0; // 初始组数为0
   1
   2
   3
   4

2. 为每个组初始化结果数组和列大小数组:

   for (int i = 0; i < strsSize; i++) {
       res[i] = (char**)malloc(sizeof(char*) * strsSize);
       (*returnColumnSizes)[i] = 0;
   }
   1
   2
   3
   4

3. 处理输入字符串，将其排序并存储在结构体数组中:

   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);
   }
   1
   2
   3
   4
   5
   6

4. 根据字符串长度对结构体数组进行排序:

   qsort(str_st, strsSize, sizeof(str_t), cmp1);
   1

5. 分组字母异位词:

   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)++;
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

6. 主函数测试:

   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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24

复杂度分析

• 时间复杂度:

  • 对每个字符串排序的时间复杂度为 O(N log N)，其中 N 为字符串长度。
  • 对结构体数组进行排序的时间复杂度为 O(M log M)，其中 M 为字符串数组的大小。
  • 总时间复杂度为 O(M * N log N)，M 是字符串数组的大小，N 是最长字符串的长度。

• 空间复杂度:

  • 主要由存储结果的二维数组 res 和辅助数组 str_st 组成。总体空间复杂度为 O(M * N)。

结果