回文最少分割

[编程题]回文最少分割

热度指数：1727 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串，返回把str全部切割成回文串的最少切割数。

输入描述:

输出包含一行字符串，代表str。

输出描述:

输出一个整数，代表把str全部切割成回文串的最小切割数。

示例1

输入

ABA

输出

说明

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

示例2

输入

ABCBAEEE

输出

说明

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

备注:

时间复杂度,额外空间复杂度。

算法知识视频讲解

JavaScript

前端笨b一枚

[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)