โปรแกรมนับจำนวนซับสตริงพาลินโดรมใน Python

สมมติว่าเรามีสตริง s ต้องหาจำนวนซับสตริงพาลินโดรมใน s

ตัวอย่าง: s = "level" ผลลัพธ์ 7 ซับสตริงพาลินโดรมคือ ["l","e","v","e","l","eve","level"]

ขั้นตอนการแก้ปัญหา (Expand Around Center)

1. ฟังก์ชัน check_palindrome(string, left, right):
   • ans = 0
   • วนลูป while left >= 0 และ right < len(s):
     • ถ้า s[left] == s[right]: ans += 1, left -= 1, right += 1
     • อื่นๆ คืนค่า ans
   • คืนค่า ans
2. จากเมธอดหลัก:
   • ans = 0
   • วนลูป char_index จาก 0 ถึง len(s)-1:
     • ans += check_palindrome(s, char_index-1, char_index+1) (ความยาวคี่)
     • ans += check_palindrome(s, char_index, char_index+1) (ความยาวคู่)
   • คืนค่า ans + len(s) (บวกตัวอักษรเดี่ยวทุกตัว)

ตัวอย่างโค้ด Python

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"))  # Output: 7

อินพุต / เอาต์พุต

Input: "level"

Output: 7