Chuỗi con Palindromic trong Python

Giả sử chúng ta có một chuỗi; chúng ta phải đếm xem có bao nhiêu chuỗi con palindromic trong chuỗi này. Các chuỗi con có chỉ số bắt đầu hoặc chỉ số kết thúc khác nhau được tính là các chuỗi con khác nhau ngay cả khi chúng chứa các ký tự giống nhau. Vì vậy, nếu đầu vào là “aaa”, thì đầu ra sẽ là 6 vì có sáu chuỗi con palindromic như “a”, “a”, “a”, “aa”, “aa”, “aaa”

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

• số lượng:=0
• cho tôi trong phạm vi từ 0 đến độ dài nếu chuỗi
  • cho j trong phạm vi i + 1 đến độ dài của chuỗi + 1
    • temp:=chuỗi con từ chỉ mục i đến j
    • nếu nhiệt độ là palindrome, thì hãy tăng số lượng lên 1
• bộ đếm trả lại

Ví dụ (Python)

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

class Solution:
   def countSubstrings(self, s):
      counter = 0
      for i in range(len(s)):
         for j in range(i+1,len(s)+1):
            temp = s[i:j]
            if temp == temp[::-1]:
               counter+=1
      return counter
ob1 = Solution()
print(ob1.countSubstrings("aaaa"))

Đầu vào

"aaaa"

Đầu ra

10