สตริงย่อยแบบพาลินโดรมใน Python

สมมติว่าเรามีสตริง เราต้องนับว่ามีสตริงย่อยแบบพาลินโดรมกี่ตัวในสตริงนี้ สตริงย่อยที่มีดัชนีเริ่มต้นหรือสิ้นสุดต่างกันจะนับเป็นสตริงย่อยที่ต่างกัน แม้จะประกอบด้วยตัวอักษรเดียวกัน ดังนั้นถ้าอินพุตคือ "aaa" ผลลัพธ์จะเป็น 6 เพราะมีสตริงย่อยพาลินโดรม 6 ตัวคือ "a", "a", "a", "aa", "aa", "aaa"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ −

count := 0
for i ในช่วง 0 ถึงความยาวของสตริง
- for j ในช่วง i + 1 ถึงความยาวของสตริง + 1
  - temp := สตริงย่อยจากดัชนี i ถึง j
  - ถ้า temp เป็นพาลินโดรม ให้เพิ่ม count ขึ้น 1
คืนค่า counter

ตัวอย่าง (Python)

มาดูการนำไปใช้เพื่อความเข้าใจที่ดีขึ้น −

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

อินพุต

"aaaa"