原题地址：https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/
题解
每次固定左边界（leftEdge）和右边界（rightEdge），左边界以左和右边界以右的部分是已经遍历完毕的部分；
判断[leftEdge,i]和[j,rightEdge]之间的部分是否相等
- 若不相等则i++，j–，最终必然会遍历到相等的情况（[leftEdge,i]和[j,rightEdge]是同一索引或相邻区间的情况，即abcba和abccba）
- 若相等则重置leftEdge为i+1，rightEdge为j-1，然后ans++
时间复杂度：O(N^2)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int longestDecomposition(String text) {
int leftEdge=0,rightEdge=text.length()-1;
int i,j,k,ans=0;
boolean isEqual;
while(leftEdge<=rightEdge){
isEqual=false;
i=leftEdge;
j=rightEdge;
while(!isEqual){
for(k=0;j+k<=rightEdge;k++){
if(text.charAt(leftEdge+k)!=text.charAt(j+k)){
isEqual=false;
break;
}
isEqual=true;
}
if(isEqual==false){
i++;
j--;
}else{
if(i==rightEdge||j==leftEdge){
leftEdge=999;
rightEdge=0;
ans+=1;
}else{
leftEdge=i+1;
rightEdge=j-1;
ans+=2;
}
}
}
}
return ans;
}
}
|
