Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PalindromePartitioning {
    public static void main(String[] args) {
        String str = "aab";
        List<List<String>> part = partition(str);
        System.out.println(Arrays.asList(part));
    }
    // function to check if string
    // is palindrome or not
    static boolean isPalindrome(String s) {
        int low = 0;
        int high = s.length() - 1;
        while (low < high) {
            if (s.charAt(low) != s.charAt(high))
                return false;
            low++;
            high--;
        }
        return true;
    }
    // partitions the strings
    static void partitions(String s, List<String> partial) {
        // base case
        // if there is nothing left then push the partial 
           //ans to the main ans(res)
        if (s.length() == 0) {
            List<String> l = new ArrayList<>();
            l.addAll(partial);
            res.add(l);
        }
        else {
            // check for all substring for palindrome
            for (int i = 0; i < s.length(); i++) {
                String left = s.substring(0, i + 1);
                String right = s.substring(i + 1);
                if (isPalindrome(left)) {
                    // push the current palindrome into partial ans
                    partial.add(left);
                    // recurr for right part
                    partitions(right, partial);
                    // backtracking
                    partial.remove(partial.size() - 1);
                }
            }
        }
    }
    static List<List<String>> res;
    static List<List<String>> partition(String s) {
        res = new ArrayList<List<String>>();
        List<String> partial = new ArrayList<>();
        partitions(s, partial);
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to check if string
//is palindrome or not
bool isPalindrome(string s)
{
    int low=0;
    int high=s.size()-1;
    while(low<high)
        {
            if(s[low]!=s[high])
                  return false;
            low++;
            high--;
        }
    return true;
}
//partitions the strings
void partitions(string s,vector<vector<string>>&res,vector<string> &partial)
{
        //base case
        //if there is nothing left then push the partial ans to the main ans(res)
        if(s.size()==0)
            res.push_back(partial);
     
        else
        {
            //check for all substring for palindrome
            for(int i=0;i<s.size();i++)
            {
                string left=s.substr(0,i+1);
                string right=s.substr(i+1);
                if(isPalindrome(left))
                {
                    //push the current palindrome into partial ans
                    partial.push_back(left);
                    //recurr for right part
                    partitions(right,res,partial);
                    //backtracking
                    partial.pop_back();
                }
            
            }
       }
}
vector<vector<string>> partition(string s) 
{
        vector<vector<string>> res;
        vector<string> partial;
        partitions(s,res,partial);
        return res;
}
int main()
{
    string str="aab";
    vector<vector<string>> part=partition(str);
    cout<<"[";
    for(int i=0;i<part.size();i++)
      {
          cout<<"[";
          for(int j=0;j<part[i].size();j++)
             {
                cout<<part[i][j];
                if(j!=part[i].size()-1)
                  cout<<",";
             }
            cout<<"]";
            if(i!=part.size()-1)
              cout<<",";
      }
     cout<<"]";
    return 0;
}