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.

&nbsp;
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]

&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 16
	s contains only lowercase English letters.


"""
we can approach this problem using manacher's algorithm with backtracking and recursion
"""
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        lookup = {"": [[]]}
        def lps(s):
            if s in lookup:
                return lookup[s]

            final_res = []
            result_set = set()
            for k in range(len(s)):
                i, j = k, k

                # check for odd length palindromes
                while i>= 0 and j < len(s) and s[i] == s[j]:
                    # palindrome found
                    res = []
                    for partition in lps(s[:i]):
                        res.append(partition + [s[i:j+1]])
                    for partition in res:
                        for part in lps(s[j+1:]):
                            temp = partition + part
                            if tuple(temp) not in result_set:
                                result_set.add(tuple(temp))
                                final_res.append(temp)
                    i-=1
                    j+=1

                # check for even length palindromes
                i, j = k, k+1
                while i >= 0 and j < len(s) and s[i] == s[j]:
                    # palindrome found
                    res = []
                    for partition in lps(s[:i]):
                        res.append(partition + [s[i:j+1]])
                    for partition in res:
                        for part in lps(s[j+1:]):
                            temp = partition + part
                            if tuple(temp) not in result_set:
                                result_set.add(tuple(temp))
                                final_res.append(temp)
                    i-=1
                    j+=1
            lookup[s] = final_res
            return final_res
        return lps(s)
// Plaindrome Partitioning
// Leetcode : https://leetcode.com/problems/palindrome-partitioning/

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if(s == null || s.length() == 0)
            return result;
        helper(s, 0, new ArrayList<String>(), result);
        return result;
    }
    private void helper(String s, int start, List<String> list, List<List<String>> result){
        if(start == s.length()){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = start; i < s.length(); i++){
            if(isPalindrome(s, start, i)){
                list.add(s.substring(start, i+1));
                helper(s, i+1, list, result);
                list.remove(list.size()-1);
            }
        }
    }
    private boolean isPalindrome(String s, int start, int end){
        while(start < end){
            if(s.charAt(start++) != s.charAt(end--))
                return false;
        }
        return true;
    }
}
class Solution {
public:
    bool check(string k)
    {
        string l=k;
        reverse(l.begin(),l.end());
        if(k==l)return true;
        return false;
    }
    void solve(string &s,vector<vector<string>>&ans,
               vector<string>temp,int pos)
    {
        if(pos>=s.size()){ans.push_back(temp); return;}
        string m;
        for(int i=pos;i<s.size();i++)
        {
            m+=s[i];
            if(check(m))
            {temp.push_back(m);
            solve(s,ans,temp,i+1);
            temp.pop_back();}
        }
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>>ans;
        vector<string>temp;
        solve(s,ans,temp,0);
        return ans;
    }
};
var partition = function(s) {
    let result = []
    backtrack(0, [], s, result)
    return result
};

function backtrack(i, partition, s, result){
    if(i === s.length){
        result.push([...partition])
        return
    }

    for(let j=i;j<s.length;j++){
        let str = s.slice(i,j+1)
        if(isPal(str)){
            partition.push(str)
            backtrack(j+1, partition, s, result)
            partition.pop()
        }
    }
}

function isPal(str){
    return JSON.stringify(str.split('').reverse()) === JSON.stringify(str.split(''))
}
Palindrome Partitioning