题解 | #字符串的排列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 */
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int compare (const void * a, const void * b)
{
  return ( *(char*)a - *(char*)b );
}
/**
参数列表：
    res：返回的结果集合
    str：原串
    returnSize：结果集合的长度
    tem：排序的字符串
    temlen：排序的字符串当前的长度
    flag：判断遍历到的当前元素是否加入排序串中
*/
void dfs(char* res[], char* str, int* returnSize, char tem[], int temlen, int flag[]) {
    //当前排序的元素和字符串一样长直接返回
    if (strlen(str) == temlen) {
        //开辟新空间存储该字符串
        char* new = (char*)malloc(sizeof(char) * temlen);
        for (int i = 0; i < temlen; i++) {
            new[i] = tem[i];
        }
        res[(*returnSize)++] = new;
        temlen = 0;
        return;
    }
    //递归筛选所有排列顺序
    for (int i = 0; i < strlen(str); i++) {
        //当前元素已添加到排列集合，跳过
        if (flag[i]) {
            continue;
        }
        //筛选排列顺序，避免重复
        if (i > 0 && str[i] == str[i - 1] && !flag[i - 1]) {
            continue;
        }
        tem[temlen++] = str[i];
        flag[i] = 1;
        dfs(res, str, returnSize, tem, temlen, flag);
        //不满足条件回溯
        flag[i] = 0;
        temlen--;
    }
}

char** Permutation(char* str, int* returnSize ) {
    // write code here
    if (str == NULL) {
        *returnSize = 0;  
        return NULL;
    }
    
    //字符串长度len
    int len = strlen(str);
    //最多可能出现size种排序情况
    int size = 1;
    for (int i = 1; i <= len; i++) {
        size *= i;
    }
    //flag数组判断字符串中的字符是否已经添加到排序集合中 0：否 1：是
    int flag[len];
    memset(flag, 0, 4 * len);
    //开辟数组长度为size的空间存储所有排序情况
    char** res = (char**)malloc(sizeof(char*) * size);
    //临时存储排序情况的数组
    char tem[len];
    //字符串排序
    qsort(str, len, sizeof(char), compare);
    dfs(res, str, returnSize, tem, 0, flag);

    return res;
}