这是 LeetCode 1147 “段式回文”问题。要求将字符串分割成尽可能多的段使得这些段按顺序构成回文。问题理解段式回文定义将字符串text分割成若干子串text s1 s2 ... sk满足s1 sk, s2 s_{k-1}, ...求最大的k即最多能分成多少段例如text ghiabcdefhelloadamhelloabcdefghi分成ghi abcdef hello adam hello abcdef ghi共 7 段关键点段可以是任意长度需要从两端贪心地匹配最短的可能段因为匹配更短的段可以增加总段数核心思路贪心 双指针从两端向中间扫描维护左指针l和右指针r分别指向当前未处理部分的起始和结束维护当前左段长度len从 1 开始增加检查text[l:llen]是否等于text[r-len1:r1]如果相等则找到一段回文段ans 2两端各一段移动指针l len, r - len重置len 1如果不相等则len继续尝试更长的段当l r时结束如果最后l r说明中间剩一个段ans 1为什么贪心选择最短匹配是对的如果匹配了更长的段那么这段内部的子段就无法再拆分成更多回文段匹配最短段可以最大化总段数代码实现classSolution{publicintlongestDecomposition(Stringtext){intntext.length();intl0,rn-1;intans0;intlen1;while(lr){// 如果左右两端长度相等且子串相同if(llen-1r-len1text.substring(l,llen).equals(text.substring(r-len1,r1))){ans2;// 找到一对回文段llen;r-len;len1;// 重置长度}elseif(llen-1r-len1){// 已经到达中间剩余部分作为一段ans;break;}else{len;// 尝试更长的匹配}}returnans;}}示例演示示例1text aaa n 3 初始: l0, r2, len1 - 检查 a vs a → 相等 ans 2, l1, r1, len1 l r (1 1): - llen-1 1, r-len1 1 → 相等但中间无剩余 ans → ans3 break 输出: 3解释分成a a a示例2text antaprezatepzapreanta n 20 初始: l0, r19, len1 - a vs a → 相等 ans2, l1, r18 l1, r18, len1 - n vs t → 不等, len2 - nt vs nt → 相等 ans4, l3, r16 l3, r16, len1 - a vs a → 相等 ans6, l4, r15 l4, r15, len1 - p vs p → 相等 ans8, l5, r14 ... 继续 最终 ans11优化版本避免重复 substring每次substring会创建新字符串可以用哈希值快速比较但题目数据规模较小n ≤ 1000直接 substring 也可通过。如果需要优化可以用双哈希避免重复创建字符串classSolution{publicintlongestDecomposition(Stringtext){intntext.length();intl0,rn-1;intans0;while(lr){intlen1;while(llen-1r-len1){if(text.charAt(l)text.charAt(r-len1)text.substring(l,llen).equals(text.substring(r-len1,r1))){break;}len;}if(llen-1r-len1){ans2;llen;r-len;}else{ans;break;}}returnans;}}复杂度分析时间复杂度O(n²) 最坏情况每次只匹配长度为 1 的段需要比较 O(n) 次每次比较 O(len)空间复杂度O(1)或 O(n) 如果考虑 substring 创建的临时字符串由于 n ≤ 1000O(n²) 完全可行。总结这道题的核心是贪心地匹配最短的回文段双指针维护当前未处理部分的左右边界递增尝试段长度找到第一个匹配的段匹配成功则计数 2移动指针最后处理中间剩余部分这种贪心策略是正确的因为匹配更短的段可以让内部剩余部分有更多分割机会如果当前能匹配最短段匹配更长段不会得到更优解可以反证