# A DP Java solution with little modification to the solution of Palindrome Partitioning 1

• Here is my solution to the previous problem Palindrome Partitioning 1.

``````public static List<List<String>> partition(String s) {
if (s.isEmpty()) return new ArrayList<>();
int n = s.length();
List<List<String>>[] dp = new ArrayList[n + 1];
dp[0] = new ArrayList<>();
boolean[][] isPalindrome = new boolean[n][n];

for (int right = 0; right < s.length(); right++) {
List<List<String>> res = new ArrayList<>();
for (int left = 0; left <= right; left++) {
if (s.charAt(left) == s.charAt(right) && (right - left <= 1 || isPalindrome[left + 1][right - 1])) {
isPalindrome[left][right] = true;
for (List l : dp[left]) {
ArrayList list = new ArrayList(l);
list.add(s.substring(left, right + 1));
}
}
}
dp[right + 1] = res;
}
return dp[n];
}
``````

And I made a little modification so it can solve Palindrome Partitioning II.

``````public static int minCut(String s) {
if (s.isEmpty()) return 0;
int n = s.length();
int[] dp = new int[n];
boolean[][] isPalindrome = new boolean[n][n];

for (int right = 0; right < s.length(); right++) {
dp[right] = right;
isPalindrome[right][right] = true;
for (int left = 0; left <= right; left++) {
if (s.charAt(left) == s.charAt(right) && (right - left <= 1 || isPalindrome[left + 1][right - 1])) {
if (left == 0)
dp[right] = 0;
else {
isPalindrome[left][right] = true;
dp[right] = Math.min(dp[left - 1] + 1, dp[right]);
}
}
}
}
return dp[n - 1];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.