텍스트가 있다고 가정해 보겠습니다. 다음과 같이 a[1], a[2], ..., a[k]가 존재하도록 가능한 가장 큰 k를 찾아야 합니다. 각 a[i]는 비어 있지 않은 문자열입니다. 연결 a[1] + a[2] + ... + a[k]는 주어진 텍스트와 같습니다. 범위 1에서 k까지의 모든 i에 대해 a[i] =a[{k+1 - i}].
따라서 입력이 "antprezatepzapreanta"와 같으면 출력은 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)( a)(nt)(a)".
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
시작 :=0, 끝 :=텍스트 길이 - 1
-
빈 문자열로 temp1 및 temp2 초기화
-
ans =텍스트 길이가 홀수이면 1, 그렇지 않으면 0
-
동안 시작 <끝, 수행 -
-
temp1 :=temp1 + 텍스트[시작]
-
temp2 :=텍스트[end] + temp2
-
temp1이 temp2와 같으면 -
-
temp1 및 temp2를 빈 문자열로 설정
-
ans :=ans + 2
-
-
시작 :=시작 + 1
-
끝 :=끝 - 1
-
-
텍스트 길이가 짝수이고 (temp1 또는 temp2가 비어 있지 않은 경우)
-
ans :=ans + 1
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object):
def longestDecomposition(self, text):
start = 0
end = len(text)-1
temp1 = ""
temp2 = ""
ans = 1 if len(text) & 1 else 0
while start<end:
temp1+=text[start]
temp2 = text[end]+temp2
if temp1 == temp2:
temp1 = temp2 = ""
ans+=2
start+=1
end-=1
if len(text)%2 == 0 and(temp1 or temp2):
ans += 1
return ans
ob = Solution()
print(ob.longestDecomposition("antaprezatepzapreanta")) 입력
"antaprezatepzapreanta"
출력
11