Chương trình tìm số lượng palindromes có thể có mà chúng tôi có thể thực hiện bằng cách cắt 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 chúng ta có thể thu được một palindrome bằng cách cắt bỏ các cạnh bên trái và bên phải của s.

Vì vậy, nếu đầu vào là s =​​"momo", thì đầu ra sẽ là 6, vì Bạn có thể nhận được ["mẹ", "omo", "o", "o", "m", "m", " o ")

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm expand (). Điều này sẽ mất i, j, s

• c:=0

• while i> =0 and j

  • i:=i - 1, j:=j + 1

  • c:=c + 1

• trả lại c

• Từ phương thức chính, thực hiện như sau

• c:=0

• đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện

  • c:=c + expand (i, i, s)

  • c:=c + expand (i, i + 1, s)

• trả lại c

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"momo"

Đầu ra

6