# 131. Palindrome Partitioning (Medium)

https://leetcode.com/problems/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.

Example:

```Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
```

## Solutions

``````class Solution {

// key is the substring, value is whether it is palindrome or not.
Map<String, Boolean> validPalindromes = new HashMap<>();

// strings or substrings of them can not form the palindrome
Map<String, Boolean> unpartitionableStrs = new HashMap<>();

Map<String, List<List<String>>> solutions = new HashMap<>();

public List<List<String>> partition(String s) {
if (s == null || s.isEmpty()) {
return null;
}

// Sort out all the possible substrings that satisfy all criterion of palindrome string.
sortOutPalindrome(s);

recurse(s);

return solutions.get(s);
}

private void sortOutPalindrome(String s) {
// i is the length of palindrome
for (int i = 1; i <= s.length(); i++) {

// j is the start index of the palindrome
for (int j = 0; j < s.length() - i + 1; j++) {
String str = s.substring(j, j + i);

// every single char is a valid palindrome
if (i == 1) {
validPalindromes.put(str, true);
continue;
}

// find out all the palindrome of length 2
if (i == 2) {
if (str.charAt(0) == str.charAt(1)) {
validPalindromes.put(str, true);
} else {
validPalindromes.put(str, false);
}

continue;
}

// for length >= 3
if (!validPalindromes.get(str.substring(1, i - 1))) {
validPalindromes.put(str, false);
continue;
}

// check out if both side is equal
if (s.charAt(j) == s.charAt(j + i - 1)) {
validPalindromes.put(str, true);
}
// not equal and unable to form the palindrome
else {
validPalindromes.put(str, false);
}
}
}
}

private List<List<String>> recurse(String substr) {
List<List<String>> results = new ArrayList<>();

// partitionable, return solution of length 0.
if (substr == null || substr.isEmpty()) {
return results;
}

// unpartitionable, return null.
if (unpartitionableStrs.containsKey(substr)) {
return null;
}

if (solutions.containsKey(substr)) {
return solutions.get(substr);
}

for (int i = 0; i < substr.length(); i++) {
String str = substr.substring(0, i + 1);

// not a valid palindrome, no necessity to dig deep
if (!validPalindromes.get(str)) {
continue;
}

// tmp is the container to hold possible palindrome arrangements for substr[i+1:].
List<List<String>> tmp = recurse(substr.substring(i + 1));

// unpartitionable
if (tmp == null) {
continue;
}

// Problem occurs if we modify it directly owing to the fact that tmp is possessed substr[i+1:].
// As a consequence, we are expected to instantiate a brand new List to union str and the results in tmp.
tmp = union(tmp, str);

}

// no possible partition scheme for string s
if (results.isEmpty()) {
unpartitionableStrs.put(substr, false);

return null;
}

solutions.put(substr, results);

return results;
}

private List<List<String>> union(List<List<String>> results, String str) {
List<List<String>> ans = new ArrayList<>();

// results is empty which means it just hit the end of string.
if (results.isEmpty()) {
List<String> tmp = new ArrayList<>();

return ans;
}

for (List<String> sol : results) {
// create new container to keep values
List<String> tmp = new ArrayList<>(sol);

}

return ans;
}
}
``````