题目：
- 给定一个字符串
s，要求将s分割成一些子串，使得每个子串都是回文串。返回所有可能的分割方案。- 返回符合要求的最少分割次数。
解题思路
首先看第一个问题，将字符串进行分割，并且判断子串是否是回文串，将最终分割全为回文串的结果进行返回。判断回文串的方法比较简单，我们可以使用双指针法进行判断，如下：
public boolean isPalindrome(String s){
if(s == null) return false;
for(int i=0,j=s.length()-1;i<j;i++,j--){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
}
return true;
}
难点在于如何对字符串进行分割，和这个问题有点像的是全排列问题，但全排列关注的是在排列时在未选取队列中选取一个数来进行组合，直到未选取队列为空。本题则是根据索引对字符串进行切分，直到未切分区域为空。因此本题的解题思路也是回溯，我们可以从初始索引进行切割，直到当前的索引位置到达最大值停止切割，对每次切割的字符串进行判断是否为回文串，不是则直接跳过即可。可得代码如下：
private ArrayList<List<String>> result2 = new ArrayList<>();
public List<List<String>> partition(String s) {
backtrace(s, 0, new ArrayList<>(), new ArrayList<>());
return result2;
}
public void backtrace(String s , int cur, ArrayList<String> temp){
if(cur == s.length()) {
result2.add(new ArrayList<>(temp));
return;
}
for(int i = cur;i<s.length();i++){
String sub = s.substring(cur, i+1);
if(!isPalindrome(sub)){
continue;
}
temp.add(sub);
backtrace(s, i + 1, temp);
temp.remove(temp.size() - 1);
}
}
最终耗时7ms，上述代码每次都需要判断所截取的字符串是否为回文串，时间复杂度为
O
(
N
)
O(N)
O(N)，我们可以对上面的代码进行优化，在获取回文串的时候，我们可以采用二维dp数组的方式获取，这样每次就能以
O
(
1
)
O(1)
O(1)的时间复杂度获取是否为回文串，dp获取是否为回文串的思路如下：
- 判断字符串的
i到j区域是否为回文串，则首先判断i和j是否相同，不相同则直接返回false。 - 相同则首先判断
j到i的长度是否小于3，例如aba必然是回文串。如果不小于则dp[i][j]取决于dp[i+1][j-1]。
代码如下：
public boolean[][] isPalindrome3(String s){
int len = s.length();
boolean[][] dp = new boolean[len][len];
for(int i=len-1;i>=0;i--){
for(int j=i;j<len;j++){
if(s.charAt(i)==s.charAt(j)){
if(j-i<3){
dp[i][j] = true;
}else {
dp[i][j] = dp[i+1][j-1];
}
}else {
dp[i][j] = false;
}
}
}
return dp;
}
我们可以看到dp[i][j]是可能取决于dp[i+1][j-1]，这也就意味着我们需要先算dp[i+1]，即从后往前算，下面演示错误示范：
public boolean[][] isPalindrome(String s){
int len = s.length();
boolean[][] dp = new boolean[len][len];
for(int i=0;i<len;i++){
for(int j=0;j<=i;j++){
if(s.charAt(i)==s.charAt(j)){
if(j-i<3){
dp[i][j] = true;
}else {
dp[i][j] = dp[i+1][j-1];
}
}else {
dp[i][j] = false;
}
}
}
return dp;
}
则变更后代码变为：
private ArrayList<List<String>> result2 = new ArrayList<>();
public List<List<String>> partition(String s) {
backtrace2(s, 0, new ArrayList<>(), isPalindrome2(s));
return result2;
}
public void backtrace2(String s , int cur, ArrayList<String> temp, boolean[][] dp){
if(cur == s.length()) {
result2.add(new ArrayList<>(temp));
return;
}
for(int i = cur;i<s.length();i++){
String sub = s.substring(cur, i+1);
if(!dp[cur][i]){
continue;
}
temp.add(sub);
backtrace2(s, i + 1, temp, dp);
temp.remove(temp.size() - 1);
}
}
public boolean[][] isPalindrome2(String s){
int len = s.length();
boolean[][] dp = new boolean[len][len];
for(int i=len-1;i>=0;i--){
for(int j=i;j<len;j++){
if(s.charAt(i)==s.charAt(j)){
if(j-i<3){
dp[i][j] = true;
}else {
dp[i][j] = dp[i+1][j-1];
}
}else {
dp[i][j] = false;
}
}
}
return dp;
}
最终达到双百。接下来来看第二题，常规的思路是既然通过第一题得到了所有的结果，那么按照结果判断一下切分点不就行了~思路没错，但最终超时。
我们前面已经根据二维dp数组得到了i到j切割的字符串是否为回文串，那么我们可以直接使用动态规划得到最终切分的结果，假设以dp[i]表示从索引0-i切割字符串需要的最小切割次数，那此时我们对0-i的字符串进行切割，假设切割点为j，如果0-i本身即为回文串，那么切割次数为0，如果不是则最大切割次数即为i。此时字符串将会被切为0-j和j+1-i，此时我们只需关注j+1-i是否为回文串，因为dp[j]已经确定了，此时如果j+1-i是回文串则dp[i] = Math.min(dp[i], dp[j]+1)否则继续遍历即可，最终结果即为dp[len-1]，可得代码如下：
public int minCut(String s) {
int len = s.length();
boolean[][] isP = new boolean[len][len];
for(int i=len-1;i>=0;i--){
for(int j=i;j<len;j++){
if(s.charAt(i)==s.charAt(j)&&(j-i<3||isP[i+1][j-1])) isP[i][j] =true;
}
}
int[] dp = new int[len];
for(int i=0;i<len;i++){
if(isP[0][i]){
dp[i] = 0;
}else {
dp[i] = i;
for(int j=0;j<i;j++){
if(isP[j+1][i]) dp[i] = Math.min(dp[i], dp[j]+1);
}
}
}
return dp[len-1];
}
