首页 > 试题广场 >

回文最少分割

[编程题]回文最少分割
  • 热度指数：1693 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串，返回把str全部切割成回文串的最少切割数。

输入描述:
输出包含一行字符串，代表str。


输出描述:
输出一个整数，代表把str全部切割成回文串的最小切割数。
示例1

输入

ABA

输出

0

说明

本身是回文串，不需要切割，直接输出0
示例2

输入

ABCBAEEE

输出

1

说明

切割1次，变为“ABCBA”和“EEE”

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
Java
pein531头像 pein531
从左往右的尝试模型，用到了预处理的技巧，将验证回文串的复杂度从O(N)降低到了O(1)。首先根据尝试模型写一个递归的版本（会超时）： 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    private static boolean[][] isPalindrome;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        // 预处理，先弄一个能够查询str[i:j]是否是回文串的二维表
        int n = str.length;
        isPalindrome = new boolean[n][n];
        for(int i = 0; i < n; i++) Arrays.fill(isPalindrome[i], true);
        for(int i = n - 2; i >= 0; i--){
            for(int j = i + 1; j < n; j++)
                isPalindrome[i][j] = str[i] == str[j] && isPalindrome[i + 1][j - 1];
        }
        // 递归求解最小分割数
        System.out.println(process(str, 0));
    }
    
    private static int process(char[] str, int i) {
        if(i == str.length) return 0;
        int minCut = Integer.MAX_VALUE;
        // i依次作为str上第一段回文的结尾
        for(int end = i; end < str.length; end++)
            if(isPalindrome[i][end]) minCut = Math.min(minCut, 1 + process(str, end + 1));
        return minCut;
    }
}
process(str,i)表示的就是str从i开始，将后面切分为回文子串所需要的最少切割数，因此题目要求的就是process(str,0)。当然，我们要保证切割之后的每一段都是回文串，因此只考虑0~i已经是回文串的情况。而如果0~i已经是回文串了，就可以调用process(str,i+1)计算出将str从i+1到末尾切割成回文串的最少切割数的基础上，把0~i切出来的那一次切割加进来就行了，遍历所有可能的切割点i，选出代价最小的。然后我们根据递归的逻辑就能够改出如下的动态规划版本： 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    private static boolean[][] isPalindrome;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        // 预处理，先弄一个能够查询str[i:j]是否是回文串的二维表
        int n = str.length;
        boolean[][] isPalindrome = new boolean[n][n];
        for(int i = 0; i < n; i++) Arrays.fill(isPalindrome[i], true);
        for(int i = n - 2; i >= 0; i--){
            for(int j = i + 1; j < n; j++)
                isPalindrome[i][j] = str[i] == str[j] && isPalindrome[i + 1][j - 1];
        }
        // 动归求解最小分割数
        int[] dp = new int[n];
        for(int i = n - 1; i >= 0; i--){
            dp[i] = Integer.MAX_VALUE;
            for(int j = i; j < n; j++){
                if(isPalindrome[i][j]) dp[i] = Math.min(dp[i], j < n - 1? 1 + dp[j + 1]: 0);
            }
        }
        System.out.println(dp[0]);
    }
}

编辑于 2021-12-05 12:33:51 回复(0)
Java
眼睛想旅行121头像 眼睛想旅行121 
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine().trim();
        System.out.print(minCut(str));
    }
    public static int minCut(String str){
        if(str==null||str.equals("")){
            return 0;
        }
        char[] chas=str.toCharArray();
        int len=chas.length;
        int[] dp=new int[len+1];
        dp[len]=-1;
        boolean[][] p=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            dp[i]=Integer.MAX_VALUE;
            for(int j=i;j<len;j++){
                if(chas[i]==chas[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];
    }
}

发表于 2021-03-31 12:40:50 回复(0)
提交观点

问题信息

动态规划 分治 哈希
上传者：小小
难度：
3条回答 5649浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号