【每日一题Day175】LC1147段式回文 | 贪心 +双指针

段式回文【LC1147】

你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

• subtexti 是 非空 字符串
• 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )
• 对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立

返回k可能最大值。

• 思路

  使用双指针定位前缀后缀字符串，从小到大枚举每一个长度直至前缀后缀相等时【贪心】，在该位置进行分割，然后在剩余字符串中继续匹配最短的前缀和后缀，直至左指针大于右指针时，此时无法再进行分割

  • 由于题目要求获得最大的$k$，因此每次分割时的字符串长度该尽可能小

• 实现

  class Solution {public int longestDecomposition(String text) {int n = text.length();int l = 0, r = n - 1, len = 1;int res = 0;while (l < r - len + 1){if (text.substring(l, l + len).equals(text.substring(r - len + 1, r + 1))){res += 2;l += len;r -= len;len = 1;}else{len++;}}return res + (l <= r ? 1 : 0);}
  }
  

  • 复杂度
    • 时间复杂度：O(n2)O(n^2)O(n2)
    • 空间复杂度：$O(1)$