Backtracking: Partition string into its palindrome

Problem Statement:

You are given a string.

You need to partition the string in such a way that, each substring is a palindrome.

Example

Input: s = “abb”
Output: [[“a”,”b”,”b”],
[“a”,”bb”]]

Solution

The solution in very simple.
We will use backtracking approach to solve this problem.

First we loop through the string and check if substr(0,i) is palindrome. If it is, then we add the current prefix to the recursion list and we recurse further on the rest of the sub string: substr(i+1, length).

Then we discard the current add once we reach the end of the string.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<unordered_map>

using namespace std;

bool isPalindrome(const string& s, int start, int end) 
{
  while(start <= end) 
  {
      if(s[start++] != s[end--])
          return false;
  }
  return true;
}

void addPalindromePartitions(int index, string& s, vector<string>& path, vector<vector<string> >& ret) 
{
  if(index == s.size()) {
      ret.push_back(path);
      return;
  }
  for(int i = index; i < s.size(); ++i) {
      if(isPalindrome(s, index, i)) {
          path.push_back(s.substr(index, i - index + 1));
          addPalindromePartitions(i+1, s, path, ret);
          path.pop_back();
      }
  }
}

vector<vector<string>> partition(string s) 
{
  vector<vector<string> > ret;
  if(s.empty()) return ret;
  
  vector<string> path;
  addPalindromePartitions(0, s, path, ret);
  
  return ret;
}


int main()
{
   string s1 = "aab";

   vector<vector<string> > result = partition(s1);

   cout<<"Result = "<<endl;
   for (int i = 0; i < result.size(); i++)
    {
        for (int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << " ";
        }   
        cout << endl;
    }

    return 0;
}

Output:

Result =
a a b
aa b