Chương trình đếm số xâu con palindrome trong chuỗi bằng Python

Cho chuỗi s, đếm số lượng xâu con palindrome trong s.

Ví dụ: s = "level" → 7 (["l","e","v","e","l","eve","level"]).

Quy trình giải quyết (Mở rộng từ trung tâm)

1. Định nghĩa hàm check_palindrome(s, left, right) mở rộng từ trung tâm.
2. Với mỗi chỉ số char_index:
   • Gọi cho palindrome độ dài lẻ: check_palindrome(s, char_index-1, char_index+1).
   • Gọi cho palindrome độ dài chẵn: check_palindrome(s, char_index, char_index+1).
3. Tổng cộng thêm len(s) (các ký tự đơn lẻ).

Ví dụ mã nguồn

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

Đầu vào

"level"

Đầu ra

7