难度中等1012收藏分享切换为英文接收动态反馈
    给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
    字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

    示例 1:
    输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
    示例 2:
    输入: strs = [“”] 输出: [[“”]]
    示例 3:
    输入: strs = [“a”] 输出: [[“a”]]

    提示：

    • 1 <= strs.length <= 104
    • 0 <= strs[i].length <= 100
    • strs[i] 仅包含小写字母
    1. #define HANODELEN 700
    2. typedef struct node_t{
    3.     int index;
    4.     int key;
    5.     int cnt[27];
    6.     int rawSeq;
    7.     int colSeq;
    8.     struct node_t* next;
    9. }Node;
    11. typedef struct hanode_t{
    12.     int index;
    13.     int cnt;
    14.     Node* next;
    15. }HaNode;
    17. int hash_insert(HaNode* hanodes, Node* node){
    18.     int ret = 0;
    19.     int index = node->key%HANODELEN;
    20.     printf("hash_insert index %d\r\n", index);
    21.     HaNode* hanode = hanodes+index;
    22.     Node* curnode = hanode->next;
    23.     if(curnode==NULL)
    24.     {
    25.         node->rawSeq = hanode->index;
    26.         node->colSeq = hanode->cnt;
    27.         hanode->next = node;
    28.         hanode->cnt += 1;
    29.         return 0;
    30.     }
    31.     else
    32.     {
    33.             while(curnode)
    34.             {
    35.                 if(curnode->key==node->key && !memcmp(curnode->cnt,node->cnt, sizeof(node->cnt)))
    36.                 {
    37.                     node->rawSeq = hanode->index;
    38.                     node->colSeq = hanode->cnt;
    39.                     node->next=curnode->next;
    40.                     curnode->next=node;
    41.                     hanode->cnt += 1;
    42.                     return 0;
    43.                 }
    44.                 curnode=curnode->next;
    45.             }
    46.             node->rawSeq = hanode->index;
    47.             node->colSeq = 0;
    48.             node->next = hanode->next;
    49.             hanode->next = node;
    50.             hanode->cnt += 1;
    51.     }
    54.     printf("hanode->cnt %d\r\n", hanode->cnt);
    55.     return 0;
    56. }
    58. /**
    59.  * Return an array of arrays of size *returnSize.
    60.  * The sizes of the arrays are returned as *returnColumnSizes array.
    61.  * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
    62.  */
    63. char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
    64.     int i,j;
    65.     *returnSize=0;
    66.     HaNode* hanodes = (HaNode*)malloc(HANODELEN*sizeof(HaNode));
    67.     char*** output = NULL;
    68.     Node* nodes = malloc(strsSize*sizeof(Node));
    69.     memset(nodes, 0, strsSize*sizeof(Node));
    70.     memset(hanodes, 0, HANODELEN*sizeof(HaNode));
    71.     for(i=0; i<HANODELEN; i++)
    72.     {
    73.         hanodes[i].index=i;
    74.     }
    76.     for(i=0; i<strsSize; i++)
    77.     {
    78.         j=0;
    79.         nodes[i].index=i;
    80.         while(strs[i][j]!='\0')
    81.         {
    82.             nodes[i].key+=strs[i][j]-'a'+1;
    83.             nodes[i].cnt[strs[i][j]-'a'+1]+=1;
    84.             j++;
    85.         }
    86.     }
    88.     for(i=0; i<strsSize; i++)
    89.     {
    90.         hash_insert(hanodes, nodes+i);
    91.         printf("nodes[i].colSeq %d\r\n", nodes[i].colSeq);
    92.         if(nodes[i].colSeq==0)
    93.         {
    94.             *returnSize+=1;
    95.         }
    96.     }
    98.     int* outputColumnSizes = malloc((*returnSize)*sizeof(int*));
    99.     output = malloc(strsSize*sizeof(char**));
    100.     printf("output raw len %d\r\n", *returnSize);
    101.     #if 1
    102.     int k=0, l=0;
    103.     for(i=0; i<HANODELEN; i++)
    104.     {
    105.         Node* lastNode = NULL;
    106.         Node* curNode = hanodes[i].next;
    107.         if(curNode)
    108.         {
    109.             l=0;
    110.             printf("hanodes[i].cnt %d\r\n", hanodes[i].cnt);
    111.             output[k]=malloc(hanodes[i].cnt*sizeof(char*));
    112.             outputColumnSizes[k]=0;
    113.         }
    114.         else
    115.         {
    116.             continue;
    117.         }
    118.         while(curNode)
    119.         {
    120.             if(lastNode!=NULL && memcmp(lastNode->cnt, curNode->cnt, sizeof(curNode->cnt)))
    121.             {
    122.                 outputColumnSizes[k]=l;
    123.                 k++;
    124.                 l=0;
    125.                 output[k]=malloc(hanodes[i].cnt*sizeof(char*));
    126.             }
    127.             output[k][l]=strs[curNode->index];
    128.             printf("str %s\r\n", output[k][l]);
    129.             lastNode=curNode;
    130.             curNode=curNode->next;
    131.             l++;
    132.         }
    133.         outputColumnSizes[k]=l;
    134.         printf("k %d cnt %d\r\n", k, outputColumnSizes[k]);
    135.         k++;
    136.     }
    137.     #endif
    138.     *returnColumnSizes=outputColumnSizes;
    139.     printf("returnSize %d\r\n", *returnSize);
    140.     return output;
    141. }