Last updated on October 5th, 2024 at 05:47 pm

Here, We see Palindrome Partitioning LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Palindrome Partitioning LeetCode Solution

Problem Statement

Given a string s, partition s such that every 

substring of the partition is a 

palindrome. Return all possible palindrome partitioning of s.

Example 1:
Input: s = “aab”
Output: [[“a”,”a”,”b”],[“aa”,”b”]]

Example 2:
Input: s = “a”
Output: [[“a”]]

1. Palindrome Partitioning LeetCode Solution C++

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> pars;
        vector<string> par;
        partition(s, 0, par, pars);
        return pars;
    }
private: 
    void partition(string& s, int start, vector<string>& par, vector<vector<string>>& pars) {
        int n = s.length();
        if(start==n){
            pars.push_back(par);
        }else{
            for(int i = start ; i < n ;i ++){
               if(isPalindrome(s,start,i)){
                   par.push_back(s.substr(start,i-start+1));
                   partition(s,i+1,par,pars);
                   par.pop_back();
               }
            }
        }
    }
    
    bool isPalindrome(string& s, int l, int r) {
        while (l < r) {
            if (s[l++] != s[r--]) {
                return false;
            }
        }
        return true;
    }
};

2. Palindrome Partitioning LeetCode Solution Java

class Solution {
    int n;
    boolean[][] is_palindrome;
    String[][] substrings;

    List<List<String>> ans;

    void FindSubstrings(int ind, ArrayList<String> list) {
        if (ind == n) {
            ans.add(new ArrayList<String>(list));
            return;
        }

        for (int i = ind + 1; i <= n; i++) {
            if (!is_palindrome[ind][i]) continue;
            list.add(substrings[ind][i]);
            FindSubstrings(i, list);
            list.remove(list.size() - 1);
        }
    }

    public List<List<String>> partition(String s) {
        n = s.length();
        is_palindrome = new boolean[n + 1][n + 1];
        substrings = new String[n + 1][n + 1];
        for (int i = 0; i < n; i++) for (int j = i + 1; j <= n; j++) {
            substrings[i][j] = s.substring(i, j);
            is_palindrome[i][j] = IsPalindrome(substrings[i][j]);
        }

        ans = new ArrayList<List<String>>();
        FindSubstrings(0, new ArrayList<String>());
        return ans;
    }

    boolean IsPalindrome(String s) {
        int lower = 0;
        int higher = s.length() - 1;
        while (lower < higher) {
            if (s.charAt(lower) != s.charAt(higher)) return false;
            lower++;
            higher--;
        }
        return true;
    }
}

3. Palindrome Partitioning Solution JavaScript

var partition = function(s) {
    function isPalindrome(str) {
        let left = 0, right = str.length-1;
        while(left < right) {
            if(str[left] !== str[right]) return false
            left++;
            right--;
        }
        return true;
    }
    const result = [];
    function permute(arr, str) {
        if(!str.length) result.push(arr);
        for(let i = 1; i <= str.length; i++) {
            const subStr = str.slice(0, i);
            if(isPalindrome(subStr)) {
                permute([...arr, subStr], str.slice(i));
            }
        }
    }
    permute([], s);
    return result;    
};

4. Palindrome Partitioning Solution Python

class Solution(object):
    def partition(self, s):
        n = len(s)
        dp = [[] for _ in range(n + 1)]
        dp[n] = [[]]
        for begin in range(n - 1, -1, -1):
            for end in range(begin + 1, n + 1):
                candidate = s[begin:end]
                if candidate == candidate[::-1]:
                     for each in dp[end]:
                         new_each = [candidate]
                         new_each.extend(each)
                         dp[begin].append(new_each)
        return dp[0]