Interview question 08.07. Permutation and combination of non repeated strings DFS method

Interview questions 08.07. Permutations of non repeating strings

Permutations of non repeating strings . Write a method , Calculates all permutations of a string , Each character of the string is different .

Example 1:

Input ：S = “qwe”
Output ：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]

Example 2:

Input ：S = “ab”
Output ：[“ab”, “ba”]

The code solver is as follows , Maybe the code looks complex , Just practice more

/** * Note: The returned array must be malloced, assume caller calls free(). */
 int size;
 void dfs(int nowlen,int len,char **re,char *s,char *t,int *r){
    
     int i=0;
     if(nowlen==len){
    
         re[size]=(char *)malloc(sizeof(char)*(len+1));
         
         for(i=0;i<len;i++){
    
             re[size][i]=t[i];
             
         }
         re[size][i]='\0';
         size++;

     }
     else{
    
         for(i=0;i<len;i++){
    
             if(r[i]==1){
    
                 t[nowlen]=s[i];
                 r[i]=0;
                 dfs(nowlen+1,len,re,s,t,r);
                 r[i]=1;
             }

         }

     }

 }
 int f(int n){
    
     int re=1;
     while(n>=1){
    
         re=re*n;
         n--;
     }
     return re;
 }

char** permutation(char* S, int* returnSize){
    
    int len=strlen(S);
    char **re=(char **)malloc(sizeof(char *)*f(len));
    char* t=(char *)malloc(sizeof(char)*len);
    int *r=(int *)malloc(sizeof(int)*len);
    int i=0;
    for(i=0;i<len;i++){
    
        r[i]=1;
    }
    size=0;
     for(i=0;i<len;i++){
    
          if(r[i]==1){
    
               t[0]=S[i];
                 r[i]=0;
                 dfs(1,len,re,S,t,r);
                 r[i]=1;

          }
    }
    * returnSize=size;
    return re;


}