Chương trình tìm số lượng palindrome có thể tạo bằng cách cắt xén chuỗi trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số cách có thể được một palindrome bằng cách cắt xén (trimming) phía trái và phải của s.

Ví dụ, nếu đầu vào là s = "momo", thì đầu ra sẽ là 6, vì bạn có thể lấy ["mom", "omo", "o", "o", "m", "m", "o"]

Để giải quyết, chúng ta thực hiện các bước sau:

• Định nghĩa hàm expand(). Hàm này nhận i, j, s
• c := 0
• trong khi i >= 0 và j < kích thước của s và s[i] bằng s[j]:
  • i := i - 1, j := j + 1
  • c := c + 1
• trả về c
• Từ phương thức chính:
  • c := 0
  • với i trong khoảng 0 đến kích thước của s:
    • c := c + expand(i, i, s) # palindrome độ dài lẻ
    • c := c + expand(i, i + 1, s) # palindrome độ dài chẵn
  • trả về c

Ví dụ

def expand(i, j, s):
    c = 0
    while i >= 0 and j < len(s) and s[i] == s[j]:
        i -= 1
        j += 1
        c += 1
    return c

class Solution:
    def solve(self, s):
        c = 0
        for i in range(len(s)):
            c += expand(i, i, s)
            c += expand(i, i + 1, s)
        return c

ob = Solution()
s = "momo"
print(ob.solve(s))

Input

"momo"

Output

6