# Leetcode Palindrome Partitioning problem solution

In this Leetcode Palindrome Partitioning problem solution, we have 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.

## Problem solution in Python.

```class Solution(object):
def partition(self, s):
if not s:
return []
memo = {}
def partition(cur):
if cur==len(s):
return [[]]
if cur in memo:
return memo[cur]
res = []
for i in xrange(cur,len(s)):
if s[cur:i+1]==s[cur:i+1][::-1]:
for tmp in partition(i+1):
res.append([s[cur:i+1]]+tmp)
memo[cur] = res
return res
return partition(0)
```

## Problem solution in Java.

```class Solution {
List<List<String>> result = new ArrayList<>();

public List<List<String>> partition(String s) {
helper(s, 0, new ArrayList<>());
return result;
}

public void helper(String s, int index, List<String> combination){
if (index == s.length()) {
return;
}

for (int i = index; i < s.length(); i++) {

if (isValid(s.substring(index, i + 1))) {
combination.add(s.substring(index, i + 1));
helper(s, i + 1, combination);
combination.remove(combination.size() - 1);
}

}
}

public boolean isValid(String s){
if(s.length() == 1){
return true;
}
int left  = 0;
int right = s.length() - 1;

while(left < right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}

return true;
}
}
```

## Problem solution in C++.

```public:
vector<vector<string>> partition(string_view s) {
const int n = size(s);
auto is_poly = [](string_view str) {
for (int i = 0; i < size(str) / 2; ++i) {
if (str[i] != str[size(str) - i - 1]) {
return false;
}
}
return true;
};
vector<vector<string>> res;
function<void(int i)> backtrack;
vector<string> current;
backtrack = [&](int idx) {
if (idx == n) {
res.push_back(current);
return;
}
string str;
for (int i = idx; i < n; ++i) {
str += s[i];
if (is_poly(str)) {
current.push_back(str);
backtrack(i + 1);
current.pop_back();
}
}
};
backtrack(0);
return res;
}
```