题解 | 字符串的排列

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 */

void func(char* str,char** Res,char *res,int* flag,int inx,int* p,int len,int* returnSize)
{
    
    if(inx==len)
    {
        Res[*p]=(char*)malloc(sizeof(char)*(len+1));
        strncpy(Res[*p],res,len);
        Res[*p][len]='\0';
        (*p)++;
        *returnSize=*p;
        return;
    }

    for(int i=0;i<len;i++)
        {
            if(flag[i]==0)
            {
                // 如果当前字符与前一个字符相同，并且前一个字符已经被使用过，则跳过
                if(i>0&&str[i]==str[i-1]&&flag[i-1]==0){
                    continue;
                }
                res[inx]=str[i];
                flag[i]=1;
                func(str,Res,res,flag,inx+1,p,len,returnSize);//递归
                flag[i]=0;//回溯
            }
        }
}

int compare(const void* a,const void *b)
{
    return (*(char*)a-*(char*)b);
}

char** Permutation(char* str, int* returnSize ) {
    // write code here
    
    int len=strlen(str);
    qsort(str,len,sizeof(char),compare);

    int sum=1;
    for(int i=1;i<=len;i++)
    {
        sum*=i;
    }

    char **Res=(char**)malloc(sizeof(char*)*sum);
    char *res=(char*)malloc(sizeof(char)*(len+1));
    int *flag=(int*)malloc(sizeof(int)*len);
    memset(flag,0,sizeof(int)*len);
    int p=0;
    
    func(str,Res,res,flag,0,&p,len,returnSize);

    free(flag);
    free(res);

    return Res;
}