# LeetCode Palindrome Partitioning I and II: Backtracking (DFS) and DP

## Overview

LeetCode Palindrome Partitioning I and II: we use Backtracking (DFS) to solve the first problem and dynamic programming (DP) to tackle the second follow up.

## LeetCode Palindrome Partitioning I and II

(1)

Given a string *s*, partition *s* such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of *s*.

For example, given *s* = `"aab"`

,

Return

[ ["aa","b"], ["a","a","b"] ]

(2)

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*.

For example, given *s* = `"aab"`

,

Return `1`

since the palindrome partitioning `["aa","b"]`

could be produced using 1 cut.

## Solution and **Precautions**: Backtracking (DFS) and DP

(1) could be solve by DFS to enumerate all the possible partitions. The following Java code is accepted by LeetCode OJ to pass this Palindrome Partitioning I problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {
List<List<String>> dfs(String s, int i, boolean [][] isPalindrome) {
if (i >= s.length())
return null;
List<List<String>> result = new ArrayList<List<String>>();
for (int j = i, n = s.length(); j < n; ++j) {
if (isPalindrome[i][j]) {
String cut = s.substring(i, j + 1);
List<List<String>> others = dfs(s, j + 1, isPalindrome);
if (null != others) {
for (List<String> l : others) {
l.add(0, cut);
result.add(l);
}
}
else {
List<String> ll = new LinkedList<String>();
ll.add(cut);
result.add(ll);
}
}
}
return result;
}
public List<List<String>> partition(String s) {
int n = s.length();
boolean [][] isPalindrome = new boolean [n][n];
for (int i = 0; i < n; ++i)
for (int j = i; j >= 0; --j)
isPalindrome[i][j] = true;
for (int len = 2; len <= n; ++len)
for (int i = 0, j = i + len - 1; j < n; ++i, ++j)
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1]);
return dfs(s, 0, isPalindrome);
}
}

(2) will need to use dp for both the final result and the check of palindromic property.

Let F(i) = min cut for s[i]…s[n-1] so F(0) is our answer and we have:

F(i) = min(1 + F(j)) for j = i + 1, … n-1 and s[i]…s[j-1] is palidromic

F(i) = 0 if s[i]…s[n-1] is palindromic

To test if a substring is palindromic we again adopt dp appraoch, that is S[i]…S[j] is palindromic if and only if S[i] == S[j] and S[i+1]…S[j-1] is palindromic, the total time would be O(N^2). The following Java code is accepted by LeetCode OJ to pass this Palindrome Partitioning II problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
public int minCut(String s) {
int n = s.length();
boolean [][] isPalindrome = new boolean [n][n];
for (int i = 0; i < n; ++i)
for (int j = i; j >= 0; --j)
isPalindrome[i][j] = true;
for (int len = 2; len <= n; ++len)
for (int i = 0, j = i + len - 1; j < n; ++i, ++j)
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1]);
int [] dp = new int[n];
dp[n-1] = 0;
for (int i = n - 2; i >= 0; --i) {
if (isPalindrome[i][n-1])
dp[i] = 0;
else {
dp[i] = 1 + dp[i+1];
for (int j = i + 1; j < n; ++j) {
if (isPalindrome[i][j]) {
dp[i] = Math.min(dp[i], 1 + dp[j+1]);
}
}
}
}
return dp[0];
}
}

Remarks:

- for the dp formula, it is attempting to come up with a linear time solution by keeping the minimum cut among dp[i] … dp[n-1], but this minimum cut value is useless since the correct value depends on different cases by testing the palindrome sub-string, there is no such a constant time approach to get such minimum value to my knowledge.
- And for the first problem, do not try to copy back the results by frequently new objects in Java which might give you memory limit exceeds error from LeetCode OJ.

## Summary

LeetCode Palindrome Partitioning I and II: we use Backtracking (DFS) to solve the first problem and dynamic programming (DP) to tackle the second follow up.