• 35648

    文章

  • 23

    评论

  • 20

    友链

  • 最近新加了很多技术文章,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

leetcode: palindrome-partitioning-ii 原

欢迎来到阿八个人博客网站。本 阿八个人博客 网站提供最新的站长新闻,各种互联网资讯。 喜欢本站的朋友可以收藏本站,或者加QQ:我们大家一起来交流技术! URL链接:https://www.abboke.com/jsh/2019/0729/102465.html

挑战A.I.,赢百万奖金......了解更多详情>>>

题目描述:

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.

解题思路:

  1. 本题的题意是求给定字符串可分割成回文串的最小分割数
  2. 这题符合多阶段决策模型,所以考虑用动态规划来求解
  3. 设置一个 dp 数组,依次截取原字符串的字串来判断当前字符串的分隔条件
  4. 设立一个单独函数来判断当前字符串是否为回文串

代码如下:

    public int minCut(String s) {
        int [] dp = new int[s.length()];

	// 依次截取前 i 个字符作为当前字符串
        for(int i = 0; i < s.length(); i++){
	
	    // 如果当前字符串是回文串,那么它的可分割数是 0,否则先假设是最大的分割数 i
            dp[i] = isHuiwen(s.substring(0,i + 1)) ? 0: i;

	    // 如果当前字符串的可分割数为 0,那么它是符合题意的解,故跳过
            if(dp[i] == 0)  continue;

	    // 如果当前字符串的可分割数不是 0,则需要依次截取当前字符串的子字符串判断
            for(int j = 1; j <= i; j++){
			
		// 如果当前字符串是回文串,那么它的可分割数就需要重新给定
                if(isHuiwen(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];
    }

    // 判断当前字符串是否为回文串
    private boolean isHuiwen(String s){
        boolean flag = true;

        int i = 0;
        int j = s.length() - 1;

        while(i < j){
            if(s.charAt(i) != s.charAt(j)){
                flag = false;
                break;
            }
            i++;
            j--;
        }
        return flag;
    }

相关文章

暂住......别动,不想说点什么吗?
  • 全部评论(0
    还没有评论,快来抢沙发吧!