题解 | #字符串的排列#

对于字符串的排列，其实思路和BM56 有重复项数字的全排列是一样的，只不过BM56需要按字典升序排列，这里不需要。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 */
//check函数用于检查是否需要进行交换
int check(char* str,int left,int right)
{
    while(left<right)
    {   //如果当前检查的字符（str[left]）之后有重复的字符，那么交换是没有意义的，返回0
        if(str[left]==str[right])
        {
            return 0;
        }
        right--;
    }
  //无重复字符，交换有意义，返回1
    return 1;
}

//交换字符函数
void swap(char *str,int i,int j)
{
    char temp=str[i];
    str[i]=str[j];
    str[j]=temp;
}
//回溯递归函数
/*参数说明
  str：字符串
  strLen：字符串长度
  returnSize：当前已有解的个数（返回数组的长度）
  returnArray：返回的二维字符数组
  depth：当前进行的深度
*/

void backtrack(char *str,int strLen,int *returnSize,char **returnArray,int depth)
{   //当进行深度达到字符串长度时，表明已经达到末端，得到一种解
    if(depth==strLen)
    {   //每得到一种解，就为char类型返回数组申请一块空间，用于记录该解
        returnArray[*returnSize]=(char*)malloc(sizeof(char)*strLen);
	    //将当前字符串复制到上一步申请的空间中
        memcpy(returnArray[*returnSize],str,sizeof(char)*strLen);
	    //returnSize可以表示解的数量，所以解+1
        *returnSize=*returnSize+1;
    }
    //以下为递归过程
    else
    {
        int i;
	    //i从每一次的深度开始，往后循环查询
        for(i=depth;i<strLen;i++)
        {   //当查询该到该字符能与后面某些字符交换时，进行递归进入下一层
            if(check(str,i,strLen-1)==1)
            {   //交换
                swap(str,i,depth);
			    //递归
                backtrack(str,strLen,returnSize,returnArray,depth+1);
			    //这里是回溯出来后，要对原来的字符归零（恢复原状），所以再次交换
                swap(str,i,depth);
            }
        }
    }
}
//主函数
char** Permutation(char* str, int* returnSize ) {
    // write code here
    //申请一个二维的char类型数组，因为字符数量最多10个，所以解可能有10！种，为3628800
    char **ret=(char**)malloc(sizeof(char*)*3628801);
    //获取字符串长度
    int str_len=strlen(str);
    //初始返回char类型数组中是没有解的，设置为0
    *returnSize=0;
    //回溯开始
    backtrack(str,str_len,returnSize,ret,0);
    return ret;
}