Clean solution for the problem using recursion in C++


#1

void partpalin( int start, string& A, vector<vector>& ans, vector curr ){

if( start == A.size() ){
    
    ans.push_back( curr );
    return;
}

for( int i=start; i<A.size(); i++ ){
    
    string rev = A.substr( start, i-start+1 );
    string str = rev;
    reverse( rev.begin(), rev.end() );
    
    if( str == rev ){
        
        curr.push_back( str );
        partpalin( i+1, A, ans, curr );
        curr.pop_back();
    }
}

}

vector<vector > Solution::partition(string A) {

vector<vector<string>> ans;
vector<string> curr;
 
partpalin( 0, A, ans, curr);
 
return ans;

}


#2

hey there,
do you have a moment, can you look in my code in solution discussion, what i am doing here is, i am checking every string whether it is palindromic or not whereas you are reversing it and then comparing with the original one, can you tell me which method is best suited overall,
thanks.


#3

Hey!

I checked function ispali() in your program. You are using two pointers to check palindrome which will take half scan of the string.

Now, look into implementation of reverse.

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
  while ((first!=last)&&(first!=--last)) {
    std::iter_swap (first,last);
    ++first;
  }
}

You can see, it is also using two pointers and then swaping the elements.

So, both are doing the same work inside. It’s gonna be same i think.


#4

hey thnaks for replying,
don’t get me wrong but i think my method will be less time consuming as it will return as soon as it encounters a non palindromic situation, but on the other side your method will anyways reverse it by traversing to the half and then comparing,
what do you think?


#5

Yeah! You are right in that way.


#6

Your solution has error for the input:
“efe”


#7

I tried checking for input “efe” and this is what I got. Please check again from your end.

mysol


#8

backtrack(i+1,A,subs,n,ans); bro keep this line instead of partpalin( start+1, A, ans, curr ); this it will show correct output


#9

Thanks for the correction. In my code, i was using “i” instead of “start”. But here i got that wrong.