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

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

ดังนั้น หากอินพุตเป็น s ="ระดับ" เอาต์พุตจะเป็น 7 เนื่องจากสตริงย่อยพาลินโดรมคือ:["l","e","v","e","l","eve" ,"ระดับ"]

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

• กำหนดฟังก์ชัน check_palindrome() นี่จะเป็นสตริง ซ้าย ขวา
• ตอบ :=0
• ในขณะที่ซ้าย>=0 และขวา <ขนาดของ s ทำ
  • ถ้า s[left] เหมือนกับ s[right] แล้ว
    • อัน :=ans + 1
    • ซ้าย :=ซ้าย - 1
    • ขวา :=ขวา + 1
  • มิฉะนั้น
    • คืนสินค้า
• คืนสินค้า
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• ตอบ :=0
• สำหรับ char_index ในช่วง 0 ถึงขนาด s ทำ
  • ans :=ans + check_palindrome(s, char_index - 1, char_index + 1)
  • ans :=ans + check_palindrome(s, char_index, char_index + 1)
• ผลตอบแทน (ans) + ขนาดของ s

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

ตัวอย่าง

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

อินพุต

"level"

ผลลัพธ์

7