输出包含一行字符串,代表str。
输出一个整数,代表把str全部切割成回文串的最小切割数。
ABA
0
本身是回文串,不需要切割,直接输出0
ABCBAEEE
1
切割1次,变为“ABCBA”和“EEE”
时间复杂度,额外空间复杂度。
//思路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 }; };