[C++知识库]leetcodeOffer 38. 字符串的排列

思路

1. 全排列得回溯
2. 剪枝，当之前相等的字符串已经交换过时，剪枝

代码

void swap(char *s,int i,int j){
    char temp = s[i];
    s[i] = s[j];
    s[j] =temp;
}


void per(int start,int end,char *s,char **res,int *returnsize){
    if(start==end){
        char *re  =(char*)malloc(strlen(s)+1);
        strcpy(re,s);
        res[*returnsize] = re;
        (*returnsize)++;
        //printf("%s\n",re);
        return;
    }
    int i=0;
    for(i=start;i<end;i++){
        int flag = 1;
        for(int j = start ; j < i; j++) {//之前好的序列中已经有该字符，即遇到重复字符时不交换，直接跳过
            if(s[j]==s[i])
                flag = 0;
        }
        if (flag) {
            swap(s,i,start);//确定第一个位置后，剩下的递归找位置
            per(start+1,end,s,res,returnsize);
            swap(s,i,start);
        }

    }
}

char** permutation(char* s, int* returnSize){
    char **res = (char**) malloc(sizeof(char*)*10000);
    int i;
    *returnSize = 0;//这个地方真的坑······
    per(0,strlen(s),s,res,returnSize);
    return res;
}