131. Palindrome Partitioning LeetCode | CodingKaro

Raunit Verma January 05, 2022

131. 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"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

The solution to the above problem is

class Solution {
public:
    vector<vector<string>>ans;
    bool checkPalindrome(string s,int start,int end){
        while(start<=end){
            if(s[start]!=s[end]){
                return false;
            }
           
            start++;
            end--;
        }
        return true;
    }
    
    void helper(string s,int t,vector<string>&temp){
        if(t==s.size()){
            ans.push_back(temp);
            return;
        }
        for(int i=t; i<s.length(); i++){
            if(checkPalindrome(s,t,i)){
                temp.push_back(s.substr(t,i-t+1));
                helper(s,i+1,temp);
                temp.pop_back();
            }
        }
        
    }
    
    vector<vector<string>> partition(string s) {
        vector<string>v;
        helper(s,0,v);
        return ans;
    }
};