leetcode132. 分割回文串 II

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

思路：dp[i]代表前i个分割最小数，如果本身就是回文，那么dp[i]=0，否则它可以和任意比i小的起点组成字符串，某个字符串如果是回文，它的起点记为j，那么dp[i]就可能等于dp[j] + 1，也就是到为止的最优解加上刚发现的回文串。而最优解就是这些答案中最小的，dp[i] = Math.min(dp[i], dp[j] + 1);。

当然，检查是否是回文串是很耗时的，可以用马拉车来预先算出，这里懒得找了。

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 public int minCut(String s) {
     
    
   

    

     

    
    

     
 int len = s.length();
     
    
   

    

     

    
    

     
 if (len < 2) return 0;
     
    
   

    

     

    
    

     
 int[] dp = new int[len];
     
    
   

    

     

    
    

     
 for (int i = 0; i < len; i++) dp[i] = i;
     
    
   

    

     

    
    

     
 for (int i = 1; i < len; i++) {
     
    
   

    

     

    
    

     
 if (checkPalindrome(s, 0, i)) {
     
    
   

    

     

    
    

     

       dp[i] = 0;
     
    
   

    

     

    
    

     

       }else{
     
    
   

    

     

    
    

     
 for (int j = 0; j < i; j++)
     
    
   

    

     

    
    

     
 if (checkPalindrome(s, j + 1, i))
     
    
   

    

     

    
    

     

       dp[i] = Math.min(dp[i], dp[j] + 1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return dp[len - 1];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 private boolean checkPalindrome(String s, int left, int right) {
     
    
   

    

     

    
    

     
 while (left < right) {
     
    
   

    

     

    
    

     
 if (s.charAt(left) != s.charAt(right)) return false;
     
    
   

    

     

    
    

     

       left++;right--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104410267