首页 > 试题广场 >

分割回文串-ii

[编程题]分割回文串-ii
  • 热度指数:36960 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个字符串s,分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s="aab",
返回1,因为回文分割结果["aa","b"]是切割一次生成的。
示例1

输入

"aab"

输出

1
public class Solution {
      /**
     * 回文的最小分割数
     * 1.dp[i]表示当前i到len-1这段的最小分割数
     * 2.dp[i]=min{dp[j+1]+1}(i=<j<len)其中str[i..j]必须是回文、
     * 3.p[i][j]=true表示str[i..j]是回文
     * 4.p[i][j]=s.charAt(i)==s.charAt(j) && (j-i<2||p[i+1][j-1])
     */
    public int minCut(String s) {
        int []dp=new int[s.length()+1];
        boolean [][]p=new boolean[s.length()][s.length()];
        dp[s.length()]=-1;//确保dp[s.length()-1]=0
        for(int i=s.length()-1;i>=0;i--){
            dp[i]=Integer.MAX_VALUE;
            for(int j=i;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j) && (j-i<2||p[i+1][j-1])){
                    p[i][j]=true;
                    dp[i]=Math.min(dp[i],dp[j+1]+1);
                }
            }
        }
        return dp[0];
    }
}

发表于 2017-07-07 18:12:10 回复(15)

/**

* 动态规划的题,最主要就是写出状态转移方程
* 状态转移,其实就是怎么把一个大的状态表示为两个或者多个已知的状态
* 以此题为例,设f[i][j]为最小的切点数,那么有:
* 1、s[i][j]为回文字符串,则f[i][j] = 0;
* 2、增加一个切点p,将s[i][j]切割为两端s[i][p]、s[p+1][j],则f[i][j] = f[i][p]+f[p+1][j]
* 所谓的状态转移方程就是上面的式子
*
* 接着来看看怎么组织程序,先看看状态转移的思路:
* 以"aab"为例,"aab"明显不是回文串
* 所以 f("aab") = min( (f("a")+f("ab")) , (f("aa")+f("b")) ) + 1;
* f("a") = 0;
* f("ab") = f("a")+f("b") +1  = 0+0+1 = 1;
* f("aa") = 0;
* f("b") = 0;
* 即f("aab") = 1;
*
* 聪慧的你一定能看出来,这是一个递归调用的过程,计算f("ab")需要先计算f("a")、f("b")
* 用递归实现动态规划,在思路上是最简单的,大部分的题目都可以用这种方式解决
*
* 但是有一些数据变态的题目,加上测试机子给的堆栈太小,这种递归的算法很容易就爆栈了
* 我们需要用我们的聪明智慧,把递归的程序写为非递归的。
* 把解题思路从下往上看,假设我们先求出来了f("a"),f("b")
* 那么我们可以求出f("aa"),f("ab")
* 接着我们就可以得出答案f("aab")了
* 在这个过程中,我们需要牺牲空间(f[1000][1000])代替堆栈记录递归调用的返回值
* 而且这种方式有个好处,就是可以减少计算量
* 比如计算f("aab")时需要计算f("aa")+f("b")
* 计算f("ab")事需要计算f("a")+f("b")
* 这里就计算了两次f("b");
* 在第一次计算f("b")之后,将f("b")记录下来,可以减少一次计算量
* 动态规划本质上是暴力搜索,只不过咋这个暴力搜索的过程中,减少了不必要的计算,这样就提升了算法解决问题的速度
* 在一些题目中,你还可以根据题目减少某些分支的计算
* 比如只要判断这个字符串是回文串,就可以直接返回0,不需要一步步计算其中的子序列
*
* 写给亲爱的啊呆少女
*/

public class Solution {
private String s;
private int f[][] = new int[1000][1000];

public int minCut(String s) {
this.s = s;
//先求解小段的子序列
for(int t=0;t<=s.length();t++){
for(int i=0,j=t;j<s.length();i++,j++){
f[i][j] = compCut(i,j);
}
}
return f[0][s.length()-1];
}

// 状态转移方程的实现
public int compCut(int i,int j) {
if(isPalindrome(i,j)) return 0;
int min = s.length();
for(int p=i;p<j;p++) {
int a = f[i][p];
int b = f[p+1][j];
a = a + b + 1;
min = min<a?min:a;
}
return min;
}

//判断是否回文串
public boolean isPalindrome(int i,int j){
while(i<j) {
if(s.charAt(i) != s.charAt(j))
return false;
i++;
j--;
}
return true;
}
}
编辑于 2018-03-10 22:23:19 回复(35)
  解题思路:动态规划问题。
    dp[i] - 表示子串(0,i)的最小回文切割,则最优解在dp[s.length-1]中。
   分几种情况:
    1.初始化:当字串s.substring(0,i+1)(包括i位置的字符)是回文时,dp[i] = 0(表示不需要分割);否则,dp[i] = i(表示至多分割i次);
    2.对于任意大于1的i,如果s.substring(j,i+1)(j<=i,即遍历i之前的每个子串)是回文时,dp[i] = min(dp[i], dp[j-1]+1);
    3.如果s.substring(j,i+1)(j<=i)不是回文时,dp[i] = min(dp[i],dp[j-1]+i+1-j);

   public static int minCut(String s) {
        int[] dp = new int[s.length()];
        for(int i=0;i<s.length();i++){
        	dp[i] = isPalindrome(s.substring(0, i+1))?0:i;
        	if(dp[i] == 0)
        		continue;
        	for(int j=1;j<=i;j++){
        		if(isPalindrome(s.substring(j, i+1)))
        			dp[i] = Math.min(dp[i], dp[j-1]+1);
        		else
        			dp[i] = Math.min(dp[i], dp[j-1]+i+1-j);
        	}
        }
        return dp[dp.length-1];
    }

    //判断回文
    public static boolean isPalindrome(String s){
    	boolean flag = true;
    	for(int i=0,j=s.length()-1;i<j;i++,j--){
    		if(s.charAt(i) != s.charAt(j)){
    			flag = false;
    			break;
    		}
    	}
    	return flag;
    }

发表于 2016-06-23 11:57:18 回复(13)
/**
* 动态规划:回文的最小切割数
* 题意: 给定一个字符串s,返回把s全部切成回文子串的最小分割数。
*        例如"ABA",不需要切割,返回0;"ABCBAE",需要切割1次,成"ABCBA"和"E",返回1。
*        "ABCDE",需要切割4次,变成"A"、"B"、"C"、"D"、"E",返回4。
*
* 解:
* dp[i]表示s.substring(0, i + 1)子串的回文最小切割数,
* (Java子字符串函数满足左闭右开特点,i+1表示包含第i个字符)
* 显然最终结果为dp[s.length - 1]。
* 
* 确认初始状态:
*    dp[0] = 0,1个字符不用切割
*    当子串是回文串时,dp[i] = 0, 
*    否则dp[i]初值等于i(最坏的情况),
*    即整个子串不存在回文子字符串,需要切割i次成单个字符
* 确认状态转移方程:
*    当s.substring(j, i + 1) (1 <= j <= i)是回文时,
*    dp[i] = min(dp[i], dp[j - 1] + 1)。
*    即用变量j遍历i之前的每个子串,注意判断是否回文,是则重新给dp[i]赋值
*
* (小白一枚,借鉴了网友的思路,自己总结了一下)
**/
public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            dp[i] = isPalindrome(s.substring(0, i + 1)) ? 0 : i;
            if (dp[i] != 0) { //dp[i] = 0时不需要内循环
                for (int j = i; j > 0; j--) {
                    if (isPalindrome(s.substring(j, i + 1))) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[s.length() - 1];
    }
    
    private static boolean isPalindrome(String s) {
        int begin = 0;
        int end = s.length() - 1;
        while (begin < end) {
            if (s.charAt(begin++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
    
}

发表于 2018-10-16 16:09:10 回复(3)

定义动态规划数组dp,dp[i]的含义是子串str[0…i]至少需要切割几次,才能把str[0…i]全部切成回文子串。那么dp[len-1]就是最后的结果。

从左往右依次计算dp[i]的值,i 初始为0,具体计算过程如下:

1、假设 j 处在 0 到 i 之间,如果str[j…i]是回文串,那么dp[i]的值可能是dp[j-1] + 1,其含义是在str[0…i]上,既然str[j…i]是回文串,那么它可以自己作为一个分割的部分,剩下的部分str[0…j-1]继续做最经济的分割,也就是dp[j-1]的值。

2、根据步骤1的方式,让 j 在 i 到 0 的位置上枚举,那么所有可能中最小值就是dp[i]的值,即dp[i] = min{dp[j-1]+1 (0<= j <= i,且str[j…i]必须是回文串)}。

3、如何快速方便的判断str[j…i]是否为回文串?

 1)定义一个二维数组p,如果p[j][i]为True,表示str[j…i]是回文串,否则不是。在计算dp过程中,希望能够同步、快速的计算出矩阵p。

 2)p[j][i]如果为True,一定来自以下三种情况:
  
  <1> str[j][i]由一个字符组成
  <2> str[j][i]由两个字符组成且两个字符相等
  <3> str[j][i]由多个字符组成,str[j] == str[i]且p[j+1][i-1] == True。

 3)在计算dp数组的过程中,位置i是从左向右依次计算的。而对于每一个i来说,又依次从 i 位置向左遍历所有的位置,以此来决策dp[i]。所以对于p[j][i]来说,p[j+1][i-1]一定已经计算过。

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if(n < 2)
            return 0;
        vector<int> dp(n, INT_MAX);
        vector<bool> tmp(n, false);
        vector<vector<bool> > p(n, tmp);
        for(int i=0; i<n; i++)
        {
            for(int j=i; j>-1; j--)
            {
                if(s[i] == s[j] && (i-j < 2 || p[j+1][i-1]))
                {
                    p[j][i] = true;
                    dp[i] = min(dp[i], j == 0? 0 : dp[j-1] + 1);
                }
            }
        }
        return dp.back();
    }
};
发表于 2018-03-27 14:54:17 回复(0)
class Solution {
public:
    // 使用动态规划来做    0,1,...,i,i+1,...,j,j+1 ,如果i~j是回文,则cut[j+1] = min(cut[j+1],cut[i]+1)
    int minCut(string s)
    {
        int len = s.length();
        vector<int> minCuts(len+1);
        for(int i=0;i<=len;i++)
           minCuts[i] = i-1;
         bool dp[len][len];
        fill_n(&dp[0][0],len*len,false);
        for(int j=1;j<len;j++)
        {
            for(int i=j;i>=0;i--)
            {
                if(s[i] == s[j] && (dp[i+1][j-1] || (j-i)<2))
                {
                   dp[i][j] = true;
                   minCuts[j+1] = min(minCuts[j+1],1+minCuts[i]);
                }    
            }
        }
       return minCuts[len]; 
    }
};

发表于 2017-07-04 17:05:58 回复(0)

每次这类问题都要搞好半天... 个人感觉动归问题最难在于分析出状态转移方程。

对该问题稍加分析不难的得到如下思路:
定义f(i,j)表示字符串区间[i,j]的最小cut数目,于是转移方程为: f(i,j) = min{ f(i,k)+f(k+1,j)+1}, 0<=i <=k<j <len
1. 基于这样的思路,可以得出下面递归代码:

int minCut(string s) {
     if(isPalindrome(s)) return 0;
     set st;
     for(int i=1; i< s.size(); ++i){
        string w = s.substr(0,i);
        string left = s.substr(i);
        st.insert(minCut(w)+minCut(left)+1);
     }
      return *st.begin();
 }
 bool isPalindrome(const string& s){
     return s == string(s.rbegin(), s.rend());
 }

可惜这样做法时间复杂度太高,无法通过。需要改写为非递归形式
2
定义f(i)为字符串[i, n-1]的最小cut数目 从左往右扫描,每找到一个回文就算作一次dp,于是新状态转移方程:f(i) = min{ f(j+1)+1} ,i<=j<len
图片说明

int minCut(string s) {
        int len = s.size();
        //dp[i] 代表s.substr(i)的最小cut数目
        vector dp(len+1, 0);
        dp[len] = -1;
        for(int i=len-1; i >=0; --i){
            dp[i] = INT_MAX;
            for(int j=i+1; j<= len; ++j){
                if(isPalindrome(s.substr(i, j-i))){
                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[0];
    }
    bool isPalindrome(const string& s){
        return s == string(s.rbegin(), s.rend());
    }
编辑于 2019-01-27 22:11:46 回复(0)
    bool check(string s){
        int left=0;
        int right=s.length()-1;
        while(left<=right){
            if(s[left]!=s[right])
                break;
            left++;
            right--;
        }
        return (left>right)?true:false;
    }

    int minCut(string s) {         int lens=s.length();
        vector<int> dp(lens+1,0);
        dp[lens]=-1;
        for(int i=lens-1;i>=0;i--){
            dp[i]=INT_MAX;
            for(int j=i;j<lens;j++){
                if(check(s.substr(i,j-i+1))){
                    dp[i]=std::min(dp[i],1+dp[j+1]);
                }
            }
        }
        return dp[0];
    }

发表于 2017-11-05 10:21:28 回复(0)
int minCut(string s)
{
    int len = s.size();
    vector<vector<bool> > dp(len + 1,vector<bool>(len + 1,false));
    int f[len + 1];
    for(int i = 0; i <= len; i++)
        f[i] = len - i -1;
    for(int i = len - 1; i >= 0; i--)
    {
        for(int j = i; j < len; j++)
        {
            if(s[i] == s[j] && (j - i < 2  || dp[i + 1][j - 1]))
            {
                dp[i][j] = true;
                f[i] = min(f[i], f[j + 1] + 1);
            }
        }
    }
    return f[0];
}

发表于 2017-06-01 16:40:11 回复(0)
/*
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",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.

analysis:
定义状态数组: minCuts[n], minCuts[j]表示从0到j(包含j)的子串所需要用到的最小的切割次数
状态转移方程: 当子串str[i...j]是一个回文子串时, minCuts[j] = min(minCuts[i-1] + 1, minCuts[i])

注意的是: 

1. 此时如果i = 0, 则表示当前的str[0...j]不需要切割,即: minCuts[j] = 0;
2. 初始化和计算每一项之前都默认minCuts[j] = minCuts[j-1] + 1, 其中的原因自己分析吧;
3. 当检测到目前str[0...j]是回文的时候, 需要再一次把minCuts[j] = 0;

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <map>

using namespace std;
class Solution {
public:
    int minCut(string s) {
        int* minCuts = new int[s.length()];
        int i, j, len;

        for(minCuts[0] = 0, i = 1, len = s.length(); i < len; ++i)
        {
			if(true == palindro(s, 0, i))
				minCuts[i] = 0;
			else
				minCuts[i] = minCuts[i-1] + 1;
        }
        
        for(j = 1; j < len; ++j) {
			
			minCuts[j] = minCuts[j-1] + 1;

			for(i = j-1; i >= 0; --i) {	

				if(true == palindro(s, i, j)) {
					if(i > 0) {
						if(minCuts[j] > minCuts[i-1] + 1)
							minCuts[j] = minCuts[i-1] + 1;
					} else {
						minCuts[j] = 0;
					}
				}
				
			}
        }
        
        len = minCuts[len - 1];
        delete minCuts;
        return len;
    }
	bool palindro(string &s, int left, int right)
	{
		int i, j;
		for(i = left, j = right; i < j; ++i, --j)
		{
			if(s[i] != s[j])
			return false;
		}
		return true;
	}
		
};


发表于 2016-10-08 17:23:11 回复(1)

C++:

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        int D[len + 1];
        bool P[len][len];
        for (int i = 0; i <= len; ++i) {
            D[i] = len - i;
        }
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                P[i][j] = false;
            }
        }
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i; j < len; ++j) {
                if (s[i] == s[j] && (j - i < 2 || P[i + 1][j - 1])) {
                    P[i][j] = true;
                    D[i] = min(D[i], D[j + 1] + 1);
                }
            }
        }
        return D[0] - 1;
    }
};
发表于 2017-11-01 09:05:18 回复(2)
class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        int cnts[len]; // 保存每[0, N]子串的最小切割次数
        int ishw[len][len]; // 记录每个子串是否为回文串
        for (int i = 0; i < len; i++) {
            cnts[i] = 0;
            for (int j = 0; j < len; j++) {
                ishw[i][j] = i == j ? 1 : 0;
            }
        }
        
        for (int i = 1; i < len; i++) {
            int min_v = cnts[i-1] + 1;   // s[i]为回文,初始化最小切割次数
            for (int j = i - 1; j >= 0; j--) { // 当添加一个新的字符s[i]时,检测其是否与之前的连续字符构成回文串
                if (s[j] == s[i] && (i - j <= 1 || ishw[j+1][i-1])) { // 如果与之前的连续字符为回文串
                    ishw[j][i] = 1; // 更新记录
                    min_v = min(min_v, j == 0 ? 0 : cnts[j - 1] + 1); // 则最小切割次数为cnts[0, j-1] + 1或者是0
                }
            }
            cnts[i] = min_v; // 记录新添加一个字符后的最小切割次数
        }
        return cnts[len - 1];
    }
};

发表于 2020-04-08 22:03:50 回复(0)
这道题用动态规划来解决
1.dp数组,dp[i]表示s[0...i-1]需要分割的个数。
2.m[i][j]布尔矩阵。用来判断s[i...j]是不是回文串
int minCut(string s){
    int n = s.size();
    //dp用来保存0...i-1的分割数
    vector<int> dp(n, 0);
    //m用来表示i...j是不是回文串。
    vector<vector<bool>> m(n, vector(n,0));
    //i从0开始构建dp
    for(int i = 0; i < n; i++){
        //每次的dp[i]构建都依赖于dp[0...i-1]的值
        for(int j = i; j >= 0; j--){
           //刚开始我们假设这个dp都不是回文串。每个单词构成一个回文串。
            dp[i] = i;
            //然后判断i...j是不是回文串。
            //如果s[i] == s[j] 并且i== j。单个单词必然是回文串。如‘a'
            //如果s[i] == s[j] i = j+1; 相邻的两个相同单词必然是回文串。如’aa'
            //合并前两种情况:s[i] == s[j] && j - i < 2
            //如果超过两个单词,s[i] == s[j] && m[i][j] == true。如"a    bcb     a"
            //                                                     j m[j+1][i-1] i
            if(s[i] == s[j] && j - i < 2 || s[i] == s[j] && m[j+1][i-1]){
                //既然走到了这一步,就表明这个i到j是回文串。
                //首先m[i][j] = true;表示i...j是回文串。
                //然后在计算dp[i]的最小值。
                m[i][j] = true;
                //如果j退到了0,表明0...i整个字符串都是回文串。不需要分割。
                if(j == 0){
                    dp[i] = 0;
                }else{
                    //如果退到了j。那就是j...i是回文串。s[j....i]的分割次数是1,
                    // s[0....j-1]的分割次数是dp[j]
                    // 所以dp[i]的值就是dp[i]和 dp[j] + 1两者的最小值
                    dp[i] = min(dp[i], dp[j] + 1)
                        //到这里有人会问,dp[i] 可能会比dp[j]+1小吗?
                        //回答:可能的。因为与其说是min(dp[i], dp[j]+1)
                        //不如说是:min(dp[1]+1, dp[2]+1, dp[3]+1, dp[4] + 1, dp[5]+1,...)的最小值。
/                                               // j是从0到i的。所以每都可能会更新。
                }
            }
                
        }
        
    }
    return dp[n-1];
}
    



编辑于 2020-03-28 22:16:07 回复(2)
class Solution {
    public int minCut(String s) {
        
        /**
         *  使用动态规划寻找最优解,假设s(0,n)为字符串,s(0,i)为前i+1个字符的子串, f(i)为s(0,i)的最小分割次数
         *  问题分解为寻找一个整数j, j in [0,i], 使得s[i,j]是一个回文串,那么 f(i) = min(f(j)+1)
         *  寻找这样一个j使得f(i)最小即可, 得到状态转移方程
         *  初始赋值i=0, j=0 f(0) = 0
         *  边界值j=0, s[0,i]整个是一个回文串, f(i) = 0;
        **/
        
        // count[i] 记录 [0, i] 字符串的最小分割次数
        int[] count = new int[s.length()];
        
        // dp[j][i] 记录 [j, i] 字符串是否是回文串,已经比较过的没有必要再次比较
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        for(int i=0; i<s.length(); i++){
            // 初始化,使用Integer.MAX_VALUE也可以,但是由题目可知最大也不过 字符串长度-1
            count[i] = i;
            for(int j=0; j<=i; j++){
                // 如果s[i]==s[j],那么s[j+1,i-1]如果是回文,那么s[j,i]就是回文
                if(s.charAt(j)==s.charAt(i)&&(i-j<3||dp[j+1][i-1])){
                    dp[j][i] = true;
                    // 边界值
                    if(j==0){
                        count[i] = 0;
                        continue;
                    }
                    // f(i) = min(f(j)+1)
                    count[i] = Math.min(count[i], count[j-1]+1);
                }
            }
        }
        return count[s.length()-1];
    }
}

发表于 2020-01-03 16:27:01 回复(0)
我觉得这个题的难点在于dp数组的构建以及初始化上
public class Solution {
    //dp[i][j]表示字符串第i位到第j位分割为回文串需要的分割数
    private int[][] dp = null;
    private String s = null;
    public int minCut(String s) {
        this.s = s;
        this.dp = new int[s.length()][s.length()];
        //dp数组的初始化,00 11...01 12.。02 13...03 14...
        for(int t  = 0; t < s.length(); t++) {
            for(int i = 0,j = t; j < s.length(); i++,j++) {
                dp[i][j] = StateTransfer(i, j);
            }
        }
        return dp[0][s.length()-1];
    }
    
    //dp数组的状态转移
    public int StateTransfer(int i, int j) {
        if(i == j) return 0;
        if(judge(s.substring(i, j+1))) return 0;
        int min = s.length();
        for(int c = i; c < j; c++) {
            int a = dp[i][c];
            int b = dp[c+1][j];
            int temp = a + b + 1;
            min = min < temp ? min : temp;
        }
        return min;
    }
    
    public boolean judge(String s) {
        int len = s.length();
        for(int i = 0; i < len; i++) {
            if(s.charAt(i) != s.charAt(len-1-i)) {
                return false;
            }
        }
        return true;
    }
}


发表于 2019-12-14 17:34:57 回复(0)
public class Solution {
    public int minCut(String s) {
        int size = s.length();
        int [] dp = new int[size];
        boolean [][] isPalindrome = new boolean [size][size];
        for(int i = size - 1; i >= 0; i--){
            dp[i] = size - i;
            for(int j = i; j < size; j++){
                if(s.charAt(i) == s.charAt(j) && (j - i < 3 || isPalindrome[i + 1][j - 1])){
                    isPalindrome[i][j] = true;
                    if(j == size - 1){
                        dp[i] = 0;
                    }else if(dp[j + 1] + 1 < dp[i]){
                        dp[i] = dp[j + 1] + 1;
                    }
                }
            }
        }
        return dp[0];
    }
}

发表于 2019-10-09 20:15:16 回复(0)
class Solution {
public:
    int minCut(string s)
    {
        intlen = s.size();
        vector<int> dp(len + 1);
        for(inti = 0; i <= len; ++i)
        {
            dp[i] = i - 1;
        }
        for(inti = 0; i < len; ++i)
        {
            extend(s, i, i, dp);
            extend(s, i, i + 1, dp);
        }
        return dp[len];
    }
    void extend(string &s, int i, int j, vector<int> &dp)
    {
        for(; i >= 0 && j < s.size(); --i, ++j)
        {
            if(s[i] != s[j])
             break;
            dp[j + 1] = min(dp[j + 1], dp[i] + 1);
        }
    }
};
参考了leetcode上的解法,并使用解决回文字符串问题常用的中心扩展法修改。
发表于 2019-05-28 17:08:24 回复(0)
每次末尾加的第i个字符排法分两种
1、新加入的字符和之前的不构成回文,之前i-1的字符还是按照之前的排,
然后这时dp[i]=dp[i-1]+1;
2、新加入的字符和前面的字符构成回文,这时候找到构成回文的index,把index到i看成一个
不可分割的字符串或者把0到index看成一个字符串(前提是index到i是回文的
),这时dp[i]=dp[index]+1;
但是按照新的回文序列分割不一定就比之前的分割次数少,所以综合起来最后的
dp[i]=Math.min(dp[i-1],dp[index])+1;
这是自己推出来的,但是看大佬的解法比我的时间复杂度小很多,权当参考
import java.util.*;
public class Solution {
  public  int minCut(String s) {
      int n=s.length();
        int[] dp=new int[n+1];
        boolean[] is=new boolean[n+1];
        is[0]=true;
        dp[0]=-1;
        for(int i=1;i<=n;i++){
            String str=s.substring(0,i);
            if(ispalindrome(str))
            {
                dp[i]=0;
                is[i]=true;

            }
            else{
                int index=palindindex2(str,is);
                if(ispalindrome(str.substring(index)))
                    dp[i]=Math.min(dp[i-1],Math.min(dp[palindindex(str)],dp[index]))+1;
                else
                    dp[i]=Math.min(dp[i-1], dp[palindindex(str)])+1;
            }

        }
        return dp[n];
    }
    public int palindindex(String str){
        for(int i=0;i<str.length();i++){
            if(ispalindrome(str.substring(i))){
                return i;
            }
        }
        return str.length()-1;
    }
   public  int palindindex2(String str,boolean[] is){
        for(int i=str.length();i>0;i--){
            if(is[i]==true){
                return i;
            }
        }
        return 1;

    }
    
    public  boolean ispalindrome(String str){
        if(str.length()==1)
            return true;
       StringBuilder sb=new StringBuilder(str);
        if(str.equals(sb.reverse().toString()))
            return true;
        else
        return false;
    }
}


编辑于 2019-04-15 18:55:43 回复(0)
class Solution {
public:
    int minCut(string s) {
        if (IsPalindrome(s))
            return 0;
        for (int i = s.size()-1; i > 0; --i)
            if (IsPalindrome(s.substr(0, i)))
                return 1+minCut(s.substr(i));
    }
    
    bool IsPalindrome(const string s)
    {
        return s==string(s.rbegin(),s.rend());
    }
};  
有没有大神能帮我看看我这个代码有什么问题,在我本地的环境上把特殊情况都测试了,没问题啊,但是提交就是不通过,跪求大神解答😥
编辑于 2019-03-19 21:05:04 回复(0)
public class Solution {
    public static void main(String[] args) {
        int res = minCut("ab");
        System.out.println(res);
    }

    public static int minCut(String s) {
        int len = s.length();
        int[][] f = new int[len][len];
        for (int i = 0; i < len; i++) {
            f[i][i] = 0;
        }
        for (int i = len-1; i >= 0; i--) {
            for (int j = i+1; j < len; j++) {
                int min = Integer.MAX_VALUE;
                if(isPalindrome(s.substring(i, j+1))) {
                    min = 0;
                }
                for (int p = i; p < j; p++) {
                    int t = f[i][p] + f[p+1][j] + 1;
                    min = t < min ? t : min;
                }
                f[i][j] = min;
            }
        }
        return f[0][len-1];
    }

    private static boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r && s.charAt(l) == s.charAt(r)) {
            l++;
            r--;
        }
        if (l >= r) {
            return true;
        }
        return false;
    }
}

发表于 2018-09-21 18:14:17 回复(0)