题解 | #字符串的排列#

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

void swap(char* a, char* b) {
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void permute(char* str, int start, int end, char** result, int* returnSize) {
    if(start == end) {
        result[*returnSize] = (char*)malloc((end + 1) * sizeof(char));
        strcpy(result[*returnSize], str);
        (*returnSize)++;
    } else {
        int shouldSwap = 1;
        for(int i = start; i <= end; i++) {
            shouldSwap = 1;
            for(int j = start; j < i; j++) {
                if(str[j] == str[i]) {
                    shouldSwap = 0;
                    break;
                }
            }
            if(shouldSwap) {
                swap(&str[start], &str[i]);
                permute(str, start + 1, end, result, returnSize);
                swap(&str[start], &str[i]);
            }
        }
    }
}


char** Permutation(char* str, int* returnSize ) {
    // write code here
    int len = strlen(str);
    if(str == NULL || len == 0) {
        *returnSize = 0;
        return NULL;
    }

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

    char** result = (char**)malloc(totalPermutations * sizeof(char*));
    *returnSize = 0;
    permute(str, 0, len - 1, result, returnSize);
    return result;
}