# 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:

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:

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.