【贪心+模拟】 1147. 段式回文

【13】贪心+模拟 1147. 段式回文

Problem: 1147. 段式回文

思路

拆分字符串，使得拆分的字符串的前部分和后部分完全相同，返回能够拆分出的最大子串数

贪心：拆分时，能拆就拆=>拆分后的字符串尽可能的长=>能够拆分出尽可能多的子串

从小到大递归子串长度，模拟切割

解题方法

递归：
含义：当前字符串，能够拆分出的最大子串数
边界：不能拆=>空字符串=>长度为0

字符串的切片[(par1)..(par2)] =>[par1,par2) 左闭右开

复杂度

• 时间复杂度: O(n^2)

• 空间复杂度: O(n)

Code

s.substr(i,b): i表示从第i个位置开始选取长度为b的子串，b省略默认取到字符串末尾

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.length();
        if(n==0) return 0;//递归边界,长度为0不能拆，返回子串数为0
        for(int i = 1; i <= n/2 ; i++){//枚举前后缀长度,从小到大递归前后缀长度可以保证每次分割都是按能拆就拆的思想分割的
            if(text.substr(0,i)==text.substr(n-i)){
                return 2 + longestDecomposition(text.substr(i,n-2*i));
            }
        }
        return 1;
    }
};