1147.longest-chunked-palindrome-decomposition-cn
题目地址
https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
题目描述
Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:
Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k, a_i = a_{k+1 - i}.
Example 1:
Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".
Example 2:
Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".
Example 3:
Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".
Example 4:
Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".
Constraints:
text consists only of lowercase English characters.
1 <= text.length <= 1000
思路
给定一个字符串,让求出最多可以切成分块的回文,每一个切分可以是一个子字符串,或者单个字符。
例如, "aaaaaa"
, 可以切分成 "aaa)(aaa)" - 2
, 但是这里要求最多分块, 这样就是最多的"(a)(a)(a)(a)(a)(a)" - 6
解法一
分析, 满足回文字符串的要求是,从前读和从后读是一样的, 例如, "aba", "anna","madam"
等
那么这里就可以分别从前(l)
和从后(r)
扫描,l
和 r
记录前后扫描的index
, 然后用pre_l
and pre_r
记录前一次扫描到的可以分块的回文位置,
如果子字符串相同(substr(pre_l, l + 1)
这里包含边界),结果 +2
,继续扫描。
如果最后剩余一个(奇数个chunk), 那么直接结果 +1
, 否则偶数个chunk, 直接返回结果
例如:"volvolvo"

复杂度分析
时间复杂度:
O(N^2) - N is the s length, s.substring()时间复杂度是O(n)
空间复杂度:
O(1) - 没有额外的空间
解法二
从解法一中我们可以看到palindome
左右对称, 所以可以从左和右,用递归求解。
如下图例子, 可以从左起子字符串匹配最右起的子字符串。绿色框框,如果匹配, 递归的计算最长的回文,即每次碰到回文就计算 +2
, 直到最后字符串中没有匹配的回文,或者是匹配到最后, 退出, 返回结果。
例如:"volvolvo"

关键点分析
回文,从左到右和从右到左是一样的字符串。那么分别从左和右扫描字符串,每次遇到左右相同,则
+2
, 如果最后没有剩余字符串,则返回结果。如果最后有剩余字符或字符串,则返回结果+1
递归解类似, 同时左右对比.
代码 (Java/Python3
)
Java/Python3
)解法一
Java code
class LongestChunkedPalindromeDecomp {
public int longestDecomposition2(String text) {
if (text == null || text.length() == 0) return 0;
int l = 0;
int r = text.length() - 1;
int max = 0;
int preL = l;
int preR = r;
while (l < r) {
// prefix include right [preL, l]
String prefix = text.substring(preL, l + 1);
// suffix include right [r, preR]
String suffix = text.substring(r, preR + 1);
if (prefix.equals(suffix)) {
preL = l + 1;
preR = r - 1;
max += 2;
}
l++;
r--;
}
// check whether any string left, if so, max+1
if (preL <= preR) max++;
return max;
}
}
Python3 code
class Solution:
def longestDecomposition(self, text: str) -> int:
n = len(text)
max, l, pre_l, r, pre_r = 0, 0, 0, n - 1, n - 1
while l < r:
if text[pre_l:l + 1] == text[r:pre_r + 1]:
pre_l = l + 1
pre_r = r - 1
max += 2
l += 1
r -= 1
if pre_l <= pre_r:
max += 1
return max
解法二 - 递归
Java code
class LongestChunkedPalindromDecom {
public int longestDecomposition1(String text) {
if (text == null || text.length() == 0) return 0;
int len = text.length();
for (int i = 0; i < len / 2; i++) {
String prefix = text.substring(0, i + 1);
String suffix = text.substring(len - i - 1, len);
if (prefix.equals(suffix)) {
return 2 + longestDecomposition1(text.substring(i + 1, len - i - 1));
}
}
return 1;
}
}
Python3 code
class Solution:
def longestDecomposition(self, text: str) -> int:
n = len(text)
if not text or n == 0:
return 0
for i in range(n // 2):
if text[0:i+1] == text[n - 1 - i:n]:
return 2 + self.longestDecomposition(text[i+1:(n - 1 - i)])
return 1
Last updated
Was this helpful?