49. 字母异位词分组-排序法

49. 字母异位词分组-排序

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [“”]
输出: [[“”]]

示例 3:

输入: strs = [“a”]
输出: [[“a”]]

解题代码如下：

/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */
 int cmp(const void *a,const void *b){
    
     return *((char *)a)- *((char *)b);
 }



void quick(char **a,int low,int high ,char **b){
    
    if(low<high){
    
       // printf("%s ",a[high]);
        int l=low,h=high;
        char *ch=a[low];
        char *chb=b[low];
     
        while(low<high){
    
          // / printf("%s ",ch);
            while(low<high&&strcmp(a[high],ch)>=0){
    
              // printf("%s ",a[high]);
                high--;
            }
            a[low]=a[high];
             b[low]=b[high];

              while(low<high&&strcmp(a[low],ch)<=0){
    
                low++;
            }
            a[high]=a[low];
            b[high]=b[low];
        }
        a[low]=ch;
        b[low]=chb;
        quick(a,l,low-1,b);
        quick(a,low+1,h,b);


    }
}
char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
    
    int i;

    char **sr=(char **)malloc(sizeof( char *)*strsSize);
    char ***re=(char ***)malloc(sizeof(char **)*strsSize);

    * returnColumnSizes=(int *)malloc(sizeof(int)*strsSize);
    int size=0;

    for(i=0;i<strsSize;i++){
    
        sr[i]=(char *)malloc(sizeof(char)*(strlen(strs[i])+1));
        strcpy(sr[i],strs[i]);
        qsort(strs[i],strlen(strs[i]),sizeof(char),cmp);
    }
    quick(strs,0,strsSize-1,sr);
    char *ch=strs[0];
    int index=0;
     for(i=1;i<strsSize;i++){
    
      
      if(strcmp(strs[i],ch)!=0){
    
          int length=i-index;
          re[size]=(char**)malloc(sizeof(char *)*length);
       // printf("sdf");
          (*returnColumnSizes)[size]=length;
          int p=0;
          for(int j=index;j<i;j++){
    
              re[size][p++]=sr[j];
          }
          size++;
          index=i;
          ch=strs[i];

      }
    }
     int length=i-index;
     re[size]=(char**)malloc(sizeof(char *)*length);
       // printf("sdf");
          (*returnColumnSizes)[size]=length;
          int p=0;
          for(int j=index;j<i;j++){
    
              re[size][p++]=sr[j];
          }
          size++;
 for(i=0;i<strsSize;i++){
    
     printf("%s ",sr[i]);
 }

    * returnSize=size;
    return re;


}