TOP101题解 | BM58#字符串的排列#

#include <stdlib.h>
#include <string.h>

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


/***************************************************************************
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param str string字符串 
 * @param start 还未排序的str数组 起始下标
 * @param end 还未排序的str数组 结束下标
 * @param result 结果数组,存放每一种可能性的指针 
 * @param returnSize 返回数组行数
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 *************************************************************************/
void backtrack(char* str, int start, int end, char*** result, int* resultSize) {
    if (start == end) 
    {
        char* temp = (char*)malloc( end * sizeof(char));
        strcpy(temp, str);
        (*result)[(*resultSize)] = temp;
        (*resultSize)++;
        return;
    }
    
    for (int i = start; i <= end; i++) 
    {
        // 剪枝：如果当前字符已经在当前位置选择过了，则不需要重复选择
        bool hasDuplicate = false;
        for (int j = start; j < i; j++) 
        {
            if (str[j] == str[i]) 
            {
                hasDuplicate = true;
                break;
            }
        }
        if (hasDuplicate) 
        {
            continue;
        }
        
        swap(&str[start], &str[i]);
        backtrack(str, start + 1, end, result, resultSize);
        swap(&str[start], &str[i]);
    }
}

/***************************************************************************
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.27
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * 
 * @param str string字符串 
 * @param returnSize 返回数组行数
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 *************************************************************************/
char** Permutation(char* str, int* returnSize)
{
    int len = strlen(str);
    int capacity = 1;
    for (int i = 1; i <= len; i++) 
    {
        capacity *= i;
    }
    
    char** result = (char**)malloc(capacity * sizeof(char*));
    *returnSize = 0;
    
    backtrack(str, 0, len - 1, &result, returnSize);
    
    return result;
}