首页 > 试题广场 >

回文最少分割

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

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


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

输入

ABA

输出

0

说明

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

输入

ABCBAEEE

输出

1

说明

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

备注:
时间复杂度,额外空间复杂度
用数组dp[i]记录从第0个字符开始到当前字符最少的分割数,用数组isRound[i][j]记录第i个字符与第j个字符之间的字符是否是回文串。
从前向后遍历dp[i],内循环j从后向前遍历,寻找回文串,找到则进入设置isRound[j][i]为回文,并且设置dp[i]的值,dp[i] = min{dp[i],dp[j-1]+1},为什么是dp[j-1]+1呢,因为如果dp[j][i]为回文串则说明从str[j]之后不用分割,而dp[j-1]记录了前面j-1个字符串的最少分割数,故从j-1之后处再切一刀即可。

至于为什么要设置dp[-1]=-1,因为当整个字符串都为回文串时,dp[j-1]+1正好可以为0


#include<iostream>
#include<cstring>

using namespace std;


int main(void){
    string str;
    while(cin>>str){
        int len = str.size();
        int isRound[len][len];
        memset(isRound,0,sizeof(isRound));
        int dp[len+1];
        dp[-1] = -1;
        for(int i = 0;i<len;i++){
            dp[i] = i;
            for(int j = i;j>=0;j--){
                if(str[i]==str[j]&&(i-j<2||isRound[j+1][i-1])){
                    isRound[j][i] = 1;
                    dp[i] = (dp[i]<dp[j-1]+1?dp[i]:dp[j-1]+1);
                }
            }
            
        }
        cout<<dp[len-1]<<endl;
        
    }
}






发表于 2020-02-16 11:26:53 回复(0)
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <malloc.h>
#include <limits.h>

#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
// 初始化一个动态大小的矩阵
#define INIT_MATRIX(TYPE, PTR, COL, ROW) \
    (PTR) = (TYPE **) malloc(sizeof(TYPE *) * (COL));\
    for (int i = 0; i < (COL); i++) {\
        (PTR)[i] = (TYPE *) calloc((ROW), sizeof(TYPE));\
    }
// 释放一个动态大小的矩阵
#define FREE_MATRIX(PTR, COL) \
    for (int i = 0; i < (COL); i++) {\
        free((PTR)[i]);\
    }\
    free((PTR));
#define MAXLEN 5001


int min_cut(char *str);

int main(void) {
    char str[MAXLEN];
    scanf("%s", str);
    printf("%d\n", min_cut(str));
    return 0;
}

int min_cut(char *str) {
    int n = (int) strlen(str), res;
    int *dp = (int *) malloc(sizeof(int) * (n + 1));
    bool **is_pal;
    INIT_MATRIX(bool, is_pal, n, n);
    dp[n] = -1;
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = INT_MAX;
        for (int j = i; j < n; j++) {
            if (str[i] == str[j] && ((j - i < 2) || is_pal[i + 1][j - 1])) {
                is_pal[i][j] = true;
                dp[i] = MIN(dp[i], dp[j + 1] + 1);
            }
        }
    }
    res = dp[0];
    free(dp);
    FREE_MATRIX(is_pal, n);
    return res;
}

发表于 2022-02-11 23:16:27 回复(0)
从左往右的尝试模型,用到了预处理的技巧,将验证回文串的复杂度从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)
#include <iostream>
#include <cstring>
const int N = 5e3+2;
using namespace std;
string s;
int dp[N],can[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    int n = s.length();
    s='*'+s;
    for(int k=1;k<=n;k++){
        for(int i=1;i+k<=n;i++){
            if((can[i+1][i+k-1]||i+1>=i+k-1)&&s[i]==s[i+k])
                can[i][i+k]=1;
        }
    }
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+1;
        for(int j=1;j<=i;j++){
            if(can[j][i]||j==i){
                dp[i] = min(dp[i],dp[j-1]+1);
            }
        }
    }
    cout<<dp[n]-1<<endl;
}
发表于 2021-04-02 22:34:19 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int n = s.length();
    int a[n][n] = {0}, dp[n+1]={0};
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j] = (i==j);
            
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1] + 1;
        for(int j=i;j>=0;j--){
            if(s[i]==s[j] && (i-j<2 || a[j+1][i-1])){
                a[j][i] = 1;
                if(j==0)
                    dp[i] = min(dp[i], 0);
                else
                    dp[i] = min(dp[i], dp[j-1]+1);
            }
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

发表于 2020-05-17 01:49:49 回复(0)
#include <iostream>
(720)#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int len = s.length();
    int ishw[len][len];
    int cnt[len];
    for (int i = 0; i < len; i++) {
        cnt[i] = 0;
        for (int j = 0; j < len; j++) {
            ishw[i][j] = i == j ? 1 : 0;
        }
    }
    for (int i = 1; i < len; i++) {
        cnt[i] = cnt[i-1] + 1;
        for (int j = i; j >= 0; j--) {
            if (s[i] == s[j] && (i - j < 2 || ishw[j+1][i-1])) {
                ishw[j][i] = 1;
                cnt[i] = min(j == 0 ? 0 : cnt[j-1] + 1, cnt[i]);
            }
        }
    }
    cout << cnt[len-1] << endl;
    return 0;
}


发表于 2020-04-20 18:26:31 回复(0)
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(getHui(s));
    }
    

    public static int getHui(String s) {
        if (s == null || s.length() == 0 || s.length() == 1)
            return 0;
        char[] str = s.toCharArray();
        //dp[i]表示在str中从[i...len-1]需要的最少分割数
        int[] dp = new int[str.length+1];
        //当整串字符串为回文结构时,确保我们可以得到正确的0
        dp[str.length] = -1;
        /*
        如果在dp[i..len-1]中有j使str[i...j]为回文结构,则dp[i] = dp[j+1]+1。
        所以dp[i] = min {dp[j+1] + 1 (i<=j<len & str[i..j]是回文)}
        */
        //check[i][j] == true 代表 str[i..j]为回文
        boolean[][] check = new boolean[str.length][str.length];
        //check[i][j]为true的三种情况:
        //1. i==j; 2.j-1 == 1时两个字符相同; 3. check[i+1][j-1]==true且str[i] == str[j]
        for (int i = dp.length-2; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j < str.length; j++) {
                if(i == j)
                    check[i][j] = true;
                else if (j - i == 1)
                    check[i][j] = str[i] == str[j];
                else
                    check[i][j] = check[i+1][j-1] && str[i]==str[j];
                if(check[i][j])
                    dp[i] = Math.min(dp[i], dp[j+1] + 1);
            }
        }
        return dp[0];
    }
}

发表于 2021-08-03 15:33:14 回复(0)
【思路】:
    使用一个二维数组 boolean[][] pal  来保存字符串是否回文,在进行分割计算时直接看pal数组中对应区间是否为真,减少一趟循环,满足时间复杂度为On^2的条件;
    二维数组保存字符串回文情况:
        定义 i 从s.length-1 , j = i ,j++, j<s.length ,循环判断区间 [i+1] 到 [j-1] 是否为回文,如果此区间内为回文,且字符串的 i 下标的字符等于 j 下标的字符,则字符串为回文(原理是先判断一个较小的区间是否是回文,如果此区间回文,且区间外两端第一个元素相等,则整体回文);
转移方程:DP[i][j] : DP[i+1][j-1] && s.charAt(i) == s.charAt(j);
1、只有一个字符:
当i=j 时,表示只有一个字符,一定是回文的,
所以也代表初始状态:DP[i][j] = true;
2、只有两个字符时:
当 i+1 = j 时,表示只有两个字符,所以要判断 i 下标和 j 下标是否相等 ,相等则为回文;
3、大于两个字符,使用转移方程进行判断;
返回: 布尔矩阵。

         
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int result = minC(str);
        System.out.println(result);
    }
    
    public static boolean[][] isPal(String s) {
        boolean[][] pal = new boolean[s.length()][s.length()];
        int len = s.length();
        for(int i = len-1; i >= 0; i --) {
            for(int j = i; j < len; j ++) {
                if(i == j) {  //只有一个字符时
                    pal[i][j] = true;
                }else if(i+1 == j) {  //只有两个字符时
                    pal[i][j]= s.charAt(i)==s.charAt(j);
                }else{
                    pal[i][j] = pal[i+1][j-1] 
                        && s.charAt(i)==s.charAt(j);
                }
            }
        }
        return pal;
    }
    
    public static int minC(String str) {
        boolean[][] pal = isPal(str);  //接受保存字符串回文情况的二维数组
        int[] minC = new int[str.length()+1];
        //初始状态:
        for(int i = 0; i <= str.length(); i ++) {
            minC[i] = i-1;
        }
        //更新长度为i的最小剪切数:
        for(int i = 2; i <= str.length(); i ++) {
            //判断整体长度为i的字符串是否回文
            if(pal[0][i-1]) {  // 直接获取0-i区间的回文情况
                minC[i] = 0;
                continue;
            }
            //判断j至i区间字符串是否回文
            for(int j = 0; j < i; j ++) {
                if(pal[j][i-1]) {  // 直接获取j至i区间的回文情况
                    minC[i] = Math.min(minC[i], minC[j]+1);
                }
            }
        }
        return minC[str.length()];
    }
}

                                           
发表于 2021-06-23 15:59:54 回复(0)
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)
// JS 正确姿势
function cutStr(str) {
    const list = []; //用来存数分割后的字符串

    function checkStr(str) { //检验str是否是回文
        return str.split('').reverse().join('') === str;
    }

    var repeatCut = function (str) {
        if (checkStr(str)) { //递归出口:本身是个回文,就添加到list并返回;
            list.push(str);
            return;
        }
        for (var i = str.length; i > 0; i--) { //找出最大回文,添加到list内,剩下的继续找
            if (checkStr(str.substring(0, i + 1))) {
                list.push(str.substring(0, i + 1));
                repeatCut(str.substring(i + 1, str.length));
                break;
            }
        }
    };

    repeatCut(str);

    var count = list.length - 1;
};

编辑于 2020-10-30 09:25:52 回复(0)
[JavaScript]
//思路1:闭包+递归
function cutStr(str) {
    list = []; //用来存数分割后的字符串

    function checkStr(str) { //检验str是否是回文
        let rStr = str.split('').reverse().join('');
        if (str === rStr) {
            return true;
        }
        return false;
    }

    var repeatCut = function(str) {
        if (checkStr(str)) { //递归出口:本身是个回文,就添加到list并返回;
            list.push(str);
            return;
        }
        for (var i = str.length; i > 0; i--) { //找出最大回文,添加到list内,剩下的继续找
            if (checkStr(str.substring(0, i + 1))) {
                list.push(str.substring(0, i + 1));
                repeatCut(str.substring(i + 1, str.length));
            }
        }
    };

    repeatCut(str);

    var count = list.length - 1;
    return {
        list,
        count
    };
};


发表于 2020-04-23 17:08:58 回复(0)