Chương trình đếm số chuỗi con palindromic trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số chuỗi con palindromic trong s.

Vì vậy, nếu đầu vào là s =​​"level", thì đầu ra sẽ là 7, vì các chuỗi con palindromic là:["l", "e", "v", "e", "l", "eve" , "cấp độ"]

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

• Xác định một hàm check_palindrome (). Thao tác này sẽ lấy chuỗi, trái, phải
• ans:=0
• khi left> =0 và right
• nếu s [left] giống s [right] thì
  • ans:=ans + 1
  • left:=left - 1
  • right:=right + 1
• nếu không,
  • trả lại ans

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

Ví dụ

class Solution:
   def solve(self, s):
      def check_palindrome(string, left, right):
         ans = 0
         while left >= 0 and right < len(s):
            if s[left] == s[right]:
               ans += 1
               left -= 1
               right += 1
            else:
               return ans
         return ans
      ans = 0
      for char_index in range(len(s)):
         ans += check_palindrome(s, char_index - 1, char_index + 1)
         ans += check_palindrome(s, char_index, char_index + 1)
      return (ans) + len(s)
ob = Solution()
print(ob.solve("level"))

Đầu vào

"level"

Đầu ra

7