# 题目 131

## 描述

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

Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]


Example 2:

Input: s = "a"
Output: [["a"]]


Constraints:

1 <= s.length <= 16

s contains only lowercase English letters.

# 思路

## 拓展阅读

009-palindrome-number

125-valid-palindrome

## 核心解法

（1）判断字符串是否为回文

（2）把所有的回文子字符串都要找出来

# java 实现

## V1 基于回溯

    public List<List<String>> partition(String s) {
List<List<String>> results = new ArrayList<>();
backtrack(results, new ArrayList<>(), s, 0);
return results;
}

private void backtrack(List<List<String>> results, List<String> tempList,
String s, int startIndex) {
// 终止的条件
// 元素的長度等於 s
if(startIndex == s.length()) {
} else {
// 如何进行回溯处理呢？
for(int i = 1; i <= s.length()-startIndex; i++) {
int endIndex = startIndex + i;
String subString = s.substring(startIndex, endIndex);

if(isPalindrome(subString)) {
// 执行具体的逻辑
backtrack(results, tempList, s, endIndex);

// 回溯
tempList.remove(tempList.size()-1);
}
}
}
}

private boolean isPalindrome(String s) {
if(s.length() == 1) {
return true;
}

char[] chars = s.toCharArray();
int low = 0;
int high = chars.length-1;
while (low < high) {
if(chars[low] != chars[high] ) {
return false;
}

low++;
high--;
}

return true;
}


## V2-引入 DP 优化性能

DP 的解法，本身自己并没有意识到。

### DP 的思路

The normal dfs backtracking will need to check each substring for palindrome, but a dp array can be used to record the possible break for palindrome before we start recursion.

Edit:
Sharing my thought process:
first, I ask myself that how to check if a string is palindrome or not, usually a two point solution scanning from front and back. Here if you want to get all the possible palindrome partition, first a nested for loop to get every possible partitions for a string, then a scanning for all the partitions. That's a O(n^2) for partition and O(n^2) for the scanning of string, totaling at O(n^4) just for the partition. However, if we use a 2d array to keep track of any string we have scanned so far, with an addition pair, we can determine whether it's palindrome or not by justing looking at that pair, which is this line if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])). This way, the 2d array dp contains the possible palindrome partition among all.

second, based on the prescanned palindrome partitions saved in dp array, a simple backtrack does the job.


### 自己回文的理解

（1）场景 1

i - j <= 2 意味着两个字符的位置差为 0 1 2

（2）场景 2

### java 实现

    /**
* 思路：通过 backtrack 本身并没有问题。
*
* 但是性能这一块其实可以通过 dp 优化，通过内存记录上一次的数据，然后减少计算。
* @param s 字符串
* @return 结果
*/
public List<List<String>> partition(String s) {
List<List<String>> results = new ArrayList<>();

// 初始化 dp 数组
boolean[][] dp = new boolean[s.length()][s.length()];
// 初始化
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;
}
}
}

backtrack(dp, results, new ArrayList<>(), s, 0);
return results;
}

private void backtrack(boolean[][] dp,
List<List<String>> results,
List<String> tempList,
String s,
int startIndex) {
// 终止的条件
// 元素的長度等於 s
if(startIndex == s.length()) {
} else {
// 判断就会变得相对简单

for(int i = startIndex; i < s.length(); i++) {
// 是，则说明为回文
if(dp[startIndex][i]) {

// 执行具体的逻辑
backtrack(dp, results, tempList, s, i+1);

// 回溯
tempList.remove(tempList.size()-1);
}
}
}
}


## V3-性能还能优化吗？

// 是，则说明为回文
if(dp[startIndex][i]) {

//....
}


    /**
* 思路：通过 backtrack 本身并没有问题。
*
* 但是性能这一块其实可以通过 dp 优化，通过内存记录上一次的数据，然后减少计算。
* @param s 字符串
* @return 结果
*/
public List<List<String>> partition(String s) {
List<List<String>> results = new ArrayList<>();

// 初始化 dp 数组
boolean[][] dp = new boolean[s.length()][s.length()];
String[][] mem = new String[s.length()+1][s.length()+1];

// 初始化
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;

// 提前存储字符串
mem[j][i] = s.substring(j, i+1);
}
}
}

backtrack(mem, results, new ArrayList<>(), s, 0);
return results;
}

private void backtrack(String[][] mem,
List<List<String>> results,
List<String> tempList,
String s,
int startIndex) {
// 终止的条件
// 元素的長度等於 s
if(startIndex == s.length()) {
} else {
// 判断就会变得相对简单

for(int i = startIndex; i < s.length(); i++) {
// 是，则说明为回文
String subString = mem[startIndex][i];
if(subString != null) {

// 执行具体的逻辑
backtrack(mem, results, tempList, s, i+1);

// 回溯
tempList.remove(tempList.size()-1);
}
}
}
}


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

### EX

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.


Example 2:

Input: s = "a"
Output: 0


Example 3:

Input: s = "ab"
Output: 1


### Constraints:

1 <= s.length <= 2000

s consists of lowercase English letters only.

## V1-基础实现

    /**
* 最小砍几刀
*/
private int minCut = Integer.MAX_VALUE;

/**
* 整体思路：
*
* 1. 和原来划分的算法保持一致
*
* 2. 不过添加一个全局变量，保持 min，然后进行剪枝、
*
* @param s
* @return
*/
public int minCut(String s) {
// 本身就是，则直接返回0
if(isPalindrome(s)) {
return 0;
}

// 初始化为最大长度-1
minCut = s.length() - 1;

List<List<String>> results = new ArrayList<>();
backtrack(results, new ArrayList<>(), s, 0);

// 最多是长度-1
// 全部不同，然后拆分

return minCut;
}

private void backtrack(List<List<String>> results,
List<String> tempList,
String s, int startIndex) {

// 剪枝
if(tempList.size() > minCut) {
return;
}

// 终止的条件
// 元素的長度等於 s
if(startIndex == s.length()) {

// 更新最小值
int curTime = results.get(results.size()-1).size()  -1;
if(curTime < minCut) {
minCut = curTime;
}
} else {
// 如何进行回溯处理呢？
for(int i = 1; i <= s.length()-startIndex; i++) {
int endIndex = startIndex + i;
String subString = s.substring(startIndex, endIndex);

if(isPalindrome(subString)) {
// 执行具体的逻辑
backtrack(results, tempList, s, endIndex);

// 回溯
tempList.remove(tempList.size()-1);
}
}
}
}

private boolean isPalindrome(String s) {
if(s.length() == 1) {
return true;
}

char[] chars = s.toCharArray();
int low = 0;
int high = chars.length-1;
while (low < high) {
if(chars[low] != chars[high] ) {
return false;
}

low++;
high--;
}

return true;
}


## V2-DP 提升性能

### 思路

This can be solved by two points:

1. cut[i] is the minimum of cut[j - 1] + 1 (j <= i), if [j, i] is palindrome.

2. If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i].


The 2nd point reminds us of using dp (caching).

a   b   a   |   c  c
j  i
j-1  |  [j, i] is palindrome
cut(j-1) +  1


### java 实现

    /**
* DP思想：
*
*
* 1. 关于回文的判断，可以使用 dp
* 2. 关于最小次数，也可以使用 dp 递归。
*
* 这是一道 dp 应用比较巧妙的一道题。
*
* @param s 字符串
* @return 结果
*/
public int minCut(String s) {
// 最小砍几刀
int[] minCuts = new int[s.length()];

// 初始化 dp 数组
boolean[][] dp = new boolean[s.length()][s.length()];
// 初始化
for(int i = 0; i < s.length(); i++) {
// 最多就是和 i 一样，每个元素都拆分开。
int min = i;

// 回文判断
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;

// 如果 j 是 0，此时不需要切分。初始化的默认值
if(j == 0) {
min = 0;
} else {
// 最多切法，或者上一次最小的+1
min = Math.min(min, minCuts[j-1] + 1);
}
}
}

// 更新
minCuts[i] = min;
}

// 最后的值就是结果
return minCuts[s.length()-1];
}


# 参考资料

https://leetcode.com/problems/palindrome-partitioning-ii/solutions/42214/java-o-n-2-dp-solution/

https://leetcode.com/problems/palindrome-partitioning/description/

https://leetcode.com/problems/palindrome-partitioning/solutions/41982/java-dp-dfs-solution/

https://leetcode.com/problems/palindrome-partitioning-ii/solutions/42213/easiest-java-dp-solution-97-36/