- >`, which basically stores all the possible palindrome partition for the string s[i:n].
So, dp[n] stores all the possible palindrome partition for an empty string, which is nothing but a empty list. So, `dp[n]={}`.
If s[0:i] forms a palindrome, and if we have all the possible palindrome partition for the string s[i:n], Then by appending s[0:i] at the beginning of all the possible palindrome partition for the string s[i:n], we can get all the possible palindrome partition for the string s[0:n].
So, We will try to form every possible substring starting from start_index and ending at end_index, where `start_index <= end_index < n.` And if that substring is a palindrome, then we append that substring with all the possible palindrome partition for dp[end_index]. This will give us all possible palindromic partition for the string s[start_index:n].
We are using isPalindrome function that checks if the string with specified start and end index is a palindrome or not.
```java
class Solution {
public List

- > partition(String s) {
List

- >[] dp = new List[s.length()];
return doDp(0, dp, s);
}
private List

- > doDp(int index, List

- >[] dp, String s) {
if (index >= s.length()) {
return List.of();
}
if (dp[index] != null) return dp[index];
List

- > ans = new ArrayList<>();
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
List

- > res = doDp(i + 1, dp, s);
if (res.isEmpty()) {
ans.add(List.of(s.substring(index, i + 1)));
} else {
for (List

- > partition(String s) {
List

- >[] dp = new List[s.length()];
boolean[][] palindromeDp = new boolean[s.length()][s.length()];
for(int gap = 0; gap

- >[] dp, String s, boolean[][] palindromeDp){
if(index >= s.length()){
return List.of();
}
if(dp[index]!=null) return dp[index];
List

- > ans = new ArrayList<>();
for(int i=index; i

- > partition(String s) {
List

- > result = new ArrayList<>();
List

- > result) {
if (start >= s.length()) {
result.add(new ArrayList<>(runningList));
}
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
runningList.add(s.substring(start, end + 1));
backtrack(end + 1, s, runningList, result);
runningList.remove(runningList.size() - 1);
}
}
}
private boolean isPalindrome(String s, int start, int end) {
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) return false;
start++;
end--;
} return true;
}
}
```
### Backtracking with Palindrome DP(With Palindrome DP Calculated during Backtracking):
The Backtracking idea is the same. But instead of checking if a string starting at index i and ending at index j is a palindrome in O(n), we will be using a 2d boolean palindrome dp to store whether the string starting at index i and ending at index j is a palindrome or not.
While trying out every possible substring starting at index start_index, the end_index is in the range [start_index to n-1]. So, initially substring is of length 1, which is always true. Then when substring is of size 2, if the edge characters match it is a palindrome. And for substring of size > 3, edges must match and palindromeDp[start_index+1][end_index-1] should be true.
The reason why the `dp[start_index+1][end_index-1]` is available even when we are at start_index is because the end always starts from start which is trying to add the letter start to the list. And a single letter is always palindrome, so it recurse for start_index+1. And every possible combination of start_index+1 to end_index-1 gets calculated in this recursion. And When the recursion call returns from start_index+1, the dp[start_index+1][end_index-1] is already available for start.
```java
class Solution {
public List

- > partition(String s) {
List

- > result = new ArrayList<>();
List

- > result, boolean[][] palindromeDp) {
if (start >= s.length()) {
result.add(new ArrayList<>(runningList));
}
for (int end = start; end < s.length(); end++) {
if (s.charAt(start)==s.charAt(end) && (end-start<=2 || palindromeDp[start+1][end-1])) {
palindromeDp[start][end] = true;
runningList.add(s.substring(start, end + 1));
backtrack(end + 1, s, runningList, result,palindromeDp);
runningList.remove(runningList.size() - 1);
}
}
}
}
```
### Backtracking with Palindrome DP(With Palindrome DP Precalculated):
The idea is very similar to normal backtracking appraoch without palindrome dp.
But instead of calculating isPalindrome for every start and end index multiple times. We can use a 2d boolean dp array to store if the string from start_index to end_index forms a palindrome for every possible value of start and end index.
For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome.
Strings of length 1 are always palindrome, Strings of length 2 are palindrome only if the edge characters are same. And for length > 2, edge characters s[i] and s[j] should be same and palindrome[i+1][j-1] should be true.
So, we will take the string s on both x & y axis of the boolean array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1.
```java
class Solution {
public List

- > partition(String s) {
List

- > result = new ArrayList<>();
List

- > result, boolean[][] palindromeDp) {
if (start >= s.length()) {
result.add(new ArrayList<>(runningList));
}
for (int end = start; end < s.length(); end++) {
if (palindromeDp[start][end]) {
runningList.add(s.substring(start, end + 1));
backtrack(end + 1, s, runningList, result, palindromeDp);
runningList.remove(runningList.size() - 1);
}
}
}
}
```
## LC 132. Palindrome Partitioning II
Given a string `s`, partition `s` such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
### Recursive Top Down DP with Palindrome DP precalculated:
We can use DP to solve this problem. Here, dp[i] stores the minimum number of required partitions to partition the string s[i:n] into palindromic substrings.
And, since, it takes 0 cuts to partition an empty string into palindromic substrings, dp[n] = 0;
The dp solution is based on the idea that if s[0:i] forms a palindrome, and if dp[i] = k, then dp[0] = k+1, because if dp[i] requires k minimum cuts and s[0:i] forms a palindrome, then dp[0] will require k+1 cuts. +1 for the s[0:i] palindrome.
Now, For any given index i, there can be multiple palindrome starting at index i and ending at some later index. Lets say, There are 3 palindrome strings that starts at i and ends at j1, j2 and j3. Then, dp[i] can either be dp[j1] + 1 or dp[j2] + 1 or dp[j3] + 1. So, we take the minimum of all such possible values of dp[i], because we need to find the minimum number of partitions.
Finally, we return dp[0]-1. -1 because if there are k partitions then the cuts will be k-1.
During dp call, we need to check if a substring starting at i and ending at j forms a palindrome or not. Here we are using a pre-computed 2d palindromeDp array to store the result of isPalindrome(s, i, j).
We can use a 2d boolean dp array to store if the string from start_index to end_index forms a palindrome for every possible value of start and end index.
For any string starting at index i and ending at index j, to be palindrome, s[i]==s[j] and the middle string should be a palindrome.
Strings of length 1 are always palindrome, Strings of length 2 are palindrome only if the edge characters are same. And for length > 2, edge characters s[i] and s[j] should be same and palindromeDp[i+1][j-1] should be true.
So, we will take the string s on both x & y axis of the boolean array, Central left diagonal represents strings of gap 0, i.e strings of length 1. All diagonals on the left of the central left diagonals are not used. And all right diagonals of the central left diagonal represent gap of 1, gap of 2 and so on upto gap=n-1.
```java
class Solution {
public int minCut(String s) {
int[] dp = new int[s.length()]; // dp[i] signifies minimum partitions required to create palindrome partition using string s[i:n-1].
boolean[][] palindromeDp = new boolean[s.length()][s.length()];
for (int gap = 0; gap < s.length(); gap++) {
for (int i = 0, j = gap; j < s.length(); i++, j++) {
if (gap == 0) palindromeDp[i][j] = true;
else if (gap == 1) palindromeDp[i][j] = s.charAt(i) == s.charAt(j);
else palindromeDp[i][j] = s.charAt(i) == s.charAt(j) && palindromeDp[i + 1][j - 1];
}
}
Arrays.fill(dp,-1);
return dfsWithDp(s, 0, dp, palindromeDp) - 1; // -1 because if there are k partitions then the cuts will be k-1.
}
private int dfsWithDp(String s, int index, int[] dp, boolean[][] palindromeDp) {
if (index >= s.length()) return 0;
if(dp[index]!=-1) return dp[index];
int min = Integer.MAX_VALUE;
for (int end = index; end < s.length(); end++) {
if (palindromeDp[index][end]) {
min = Math.min(min, 1 + dfsWithDp(s, end + 1, dp, palindromeDp));
}
}
return dp[index]=min;
}
}
```
### Recursive Top Down DP with Palindrome DP calculated during main DP call:
The Dp approach is same as above. The only difference here is how palindrome dp is calculated here. Here, we will be calculating palindromDp during main dp calls.
we will be using a 2d boolean palindrome dp to store whether the string starting at index i and ending at index j is a palindrome or not.
While trying out every possible substring starting at index start_index, the end_index is in the range [start_index to n-1]. So, initially substring is of length 1, which is always true. Then when substring is of size 2, if the edge characters match it is a palindrome. And for substring of size > 3, edges must match and palindromeDp[start_index+1][end_index-1] should be true.
The reason why the `dp[start_index+1][end_index-1]` is available even when we are at start_index is because the end always starts from start which is trying to add the letter start to the list. And a single letter is always palindrome, so it recurse for start_index+1. And every possible combination of start_index+1 to end_index-1 gets calculated in this recursion. And When the recursion call returns from start_index+1, the dp[start_index+1][end_index-1] is already available for start.
```java
class SolutionTopDownDPWithPalindromeDP {
public int minCut(String s) {
int[] dp = new int[s.length()]; // dp[i] signifies minimum partitions required to create palindrome partition using string s[i:n-1].
boolean[][] palindromeDp = new boolean[s.length()][s.length()];
Arrays.fill(dp,-1);
return dfsWithDp(s, 0, dp, palindromeDp) - 1; // -1 because if there are k partitions then the cuts will be k-1.
}
private int dfsWithDp(String s, int index, int[] dp, boolean[][] palindromeDp) {
if (index >= s.length()) return 0;
if(dp[index]!=-1) return dp[index];
int min = Integer.MAX_VALUE;
for (int end = index; end < s.length(); end++) {
if (s.charAt(index)==s.charAt(end) && (end-index<=2 || palindromeDp[index+1][end-1])) {
palindromeDp[index][end]=true;
min = Math.min(min, 1 + dfsWithDp(s, end + 1, dp, palindromeDp));
}
}
return dp[index]=min;
}
}
```
### Iterative Buttom Up DP with Palindrome DP:
**Note:** We can calculate the palindromeDp either during dp calculation or precompute it. Both works as shown above. Here, we will be calculating palindromeDp during main dp. But Precompute also works here.
So, here we will be using buttom up dp to solve this problem. dp[i] stores the minimum number of palindromic partitions that the string s[i:n] can be partitioned into.
We can partition an empty string into 0 palindromic substrings, So, dp[n] = 0;
We Iterate from right to left. So, start_index ranges from n-1 to 0, and for every start_index, end_index moves from left to right and ranges from start_index to n-1.
For each such combination of start and end index, we check if s[start:end] forms a palindrome. And if it forms a palindrome, then dp[start] = Math.min(dp[start], 1 + dp[end+1]);
The dp solution is based on the idea that if s[0:i] forms a palindrome, and if dp[i] = k, then dp[0] = k+1, because if dp[i] requires k minimum cuts and s[0:i] forms a palindrome, then dp[0] will require k+1 cuts. +1 for the s[0:i] palindrome.
Now, For any given index i, there can be multiple palindrome starting at index i and ending at some later index. Lets say, There are 3 palindrome strings that starts at i and ends at j1, j2 and j3. Then, dp[i] can either be dp[j1] + 1 or dp[j2] + 1 or dp[j3] + 1. So, we take the minimum of all such possible values of dp[i], because we need to find the minimum number of partitions.
Finally, we return dp[0]-1. -1 because if there are k partitions then the cuts will be k-1.
```java
class SolutionUsingButtomUpDPWithPalindromeDP {
public int minCut(String s) {
int[] dp = new int[s.length()+1]; // dp[i] signifies minimum partitions required to create palindrome partition
boolean[][] palindromeDp = new boolean[s.length()][s.length()];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[s.length()]=0;
for(int start=s.length()-1; start>=0;start--){
for(int end = start; end