We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<stdio.h>#include<stdlib.h>#include<string.h>intnext_permutation(intn,char**s){/** * Complete this method * Return 0 when there is no next permutation and 1 otherwise * Modify array s to its next permutation *//*if lexicographically s1[] > s2[] returns 1, else 0 1<= size of s[] <= 10, s[] has only lower case English characters */intlg(char*s1,char*s2){intlen=11;intisgreater=0;for(inti=0;i<len;i++){if(s1[i]>s2[i]){isgreater=1;break;}if(s1[i]<s2[i]){isgreater=0;break;}if((s1[i]<'a')|(s1[i]>'z')){isgreater=0;break;}if((s2[i]<'a')|(s2[i]>'z')){isgreater=1;break;}}returnisgreater;}/*Step 1)search right to left and find the first item that does not follow descending order, record its indica */intind=n;//if ind does not change after for loop means there is no next permufor(inti=n-1;i>0;i--){if(lg(&(*s[i]),s[i-1])){ind=i-1;break;}}if(ind==n)return0;//there is no next permutation//Step 2) replace it with smallest greater item on the right side of it //step 2a) find smallest greater item on the right sidechar**lg_first;// = NULL;intfirst=0;intgrt=n-1;//will be the index of smallest greater item on the right sidefor(inti=n-1;i>ind;i--){if(lg(s[i],s[ind])){if(first==0){//if(lg_first == NULL){lg_first=&(s[i]);first=1;}elseif(lg(lg_first[0],s[i])){lg_first=&(s[i]);}}}//step 2b) Swapchar*temp=*(&s[ind]);s[ind]=**(&lg_first);*lg_first=temp;//step 3 Reverse the elements of the array after the item found at step 1intnext=n-1;for(inti=ind+1;i<=(((ind+n)-0)/2);i++){if(next!=i){char*temp=*(&s[next]);*(&s[next])=*(&s[i]);*(&s[i])=temp;}next--;}return1;}/***before cleaning startint next_permutation(int n, char **s){ * Complete this method * Return 0 when there is no next permutation and 1 otherwise * Modify array s to its next permutation //if lexicographically s1[] > s2[] returns 1, else 0 //1<= size of s[] <= 10, s[] has only lower case English characters int lg(char *s1, char *s2){ //size_t len1 = sizeof(s1) / sizeof(s1[0]) ; //size_t len2 = sizeof(s2) / sizeof(char*); //int len = 0; //if(len1 > len2) {len = len1;} //else {len = len2;} //printf("len1:%d len2:%d len:%d\n",len1,len2,len); //shorter lenght string olanda karakter bitti ve not greater //shorter lenght string is equal veya smaller int len = 11; int isgreater=0; for(int i=0; i<len; i++){ if(s1[i] > s2[i]) { isgreater = 1; break; } if(s1[i] < s2[i]) { isgreater = 0; break; } //if(len1 <= i+1) { // isgreater = 0; // break; //} // if(len2 <= i+1) { // isgreater = 1; // break; //} if((s1[i] < 'a') | (s1[i] > 'z')) { isgreater = 0; break; } if((s2[i] < 'a') | (s2[i] > 'z')) { isgreater = 1; break; } } return isgreater; } //Step 1)search right to left and find the first item that // does not follow descending order, record its indica int ind = n; //if ind does not change after for loop means there is no next permu for(int i=n-1;i>0;i--){ if (lg(&(*s[i]), s[i-1])){ ind = i-1; break; } } if(ind == n) return 0; //there is no next permutation//Step 2)replace it with smallest greater item on the right side of it //step 2a) find smallest greater item on the right side int dif = 0;//*s[n-1] - *s[ind]; char **lg_first;// = NULL; int first = 0; int grt = n-1; //will be the index of smallest greater item on the right side for (int i=n-1; i>ind; i--){ if( lg(s[i],s[ind]) ){ //if(lg_first == NULL){ if(first == 0){ lg_first = &(s[i]); first = 1; } else if ( lg( lg_first[0], s[i] ) ) { lg_first = &(s[i]); } } } //step 2b) Swap char *temp = *(&s[ind]); s[ind] = **(&lg_first); *lg_first = temp; //4321 //step 3 Reverse the elements of the array after the item found at step 1 int next = n-1; //for(int i=ind+1; i<n-1; i++){ for(int i=ind+1; i<=(((ind+n)-0 )/2); i++){ if(next != i){ char *temp = *(&s[next]); *(&s[next]) = *(&s[i]); *(&s[i]) = temp; } next--; }return 1; Step 1)search right to left and find the first item that does not follow descending order, record its indica ex1: s[a,b,c,d] s[3] ex2: s[a,b,d,c] s[1] ex3: s[a,c,b,d] s[3] Step 2)replace it with smallest greater item on the right side of it ex1: s[a,b,c,d] s[3] is first out of asc order, s[4] is smallest greater of s[3] so swap s[3] with s[4], string becames s'[a,b,d,c] ex2: s[a,B,d,c] s[1] is first out of asc order, s[0] is smallest greater of s[1] so swap s[0] with s[1], string becames s'[a,c,d,b] Step 3) after swapping reverse the string after the item found in Step 1) ex1: reverse after s[3] there is nothing to reverse ex2: reverse after s[1] s''[a,c,b,d]}before cleaning end */
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Permutations of Strings
You are viewing a single comment's thread. Return to all comments →
Here is my solution: