Giả sử ta có một văn bản. Ta cần tìm k lớn nhất sao cho tồn tại a[1], a[2], ..., a[k] thỏa mãn: Mỗi a[i] là chuỗi không rỗng; Nối a[1] + a[2] + ... + a[k] bằng văn bản cho trước; Với mọi i từ 1 đến k, a[i] = a[k+1-i].
Ví dụ, nếu đầu vào là "antaprezatepzapreanta", đầu ra sẽ là 11, vì ta có thể tách như "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".
Để giải quyết, ta thực hiện các bước sau:
- start := 0, end := độ dài text - 1
- Khởi tạo temp1 và temp2 bằng chuỗi rỗng
- ans = 1 nếu độ dài text lẻ, ngược lại 0
- Khi start < end, thực hiện:
- temp1 := temp1 + text[start]
- temp2 := text[end] + temp2
- Nếu temp1 bằng temp2, thì:
- Đặt temp1 và temp2 về chuỗi rỗng
- ans := ans + 2
- start := start + 1
- end := end - 1
- Nếu độ dài text chẵn và (temp1 hoặc temp2 không rỗng):
- ans := ans + 1
- Trả về ans
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
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"))Đầu vào
"antaprezatepzapreanta"
Đầu ra
11