สมมติว่าเรามีข้อความ เราต้องหา k ที่ใหญ่ที่สุดเท่าที่จะเป็นไปได้ซึ่งมีอยู่ a[1], a[2], ..., a[k] เช่นนั้น:แต่ละ a[i] เป็นสตริงที่ไม่ว่าง การต่อกัน a[1] + a[2] + ... + a[k] เท่ากับข้อความที่กำหนด สำหรับ i ทั้งหมดในช่วง 1 ถึง k, a[i] =a[{k+1 - i}].
ดังนั้น ถ้าอินพุตเป็นเหมือน "antaprezatepzapreanta" ผลลัพธ์จะเป็น 11 เพราะเราสามารถแยกออกเป็น "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)( ก)(nt)(ก)".
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
start :=0, end :=length of text - 1
-
เริ่มต้น temp1 และ temp2 ด้วยสตริงว่าง
-
ans =1 เมื่อความยาวของข้อความเป็นเลขคี่ มิฉะนั้น 0
-
ในขณะที่เริ่ม <สิ้นสุด ทำ -
-
temp1 :=temp1 + text[start]
-
temp2 :=text[end] + temp2
-
ถ้า temp1 เหมือนกับ temp2 แล้ว −
-
ตั้งค่า temp1 และ temp2 เป็นสตริงว่าง
-
ans :=ans + 2
-
-
start :=start + 1
-
end :=end - 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
