โปรแกรมหาจำนวนวิธีที่เราสามารถแยก palindrome ใน python

สมมติว่าเรามีสตริง s เราต้องหาจำนวนวิธีที่เราสามารถแบ่งพาร์ติชันสตริงได้ โดยแต่ละส่วนจะเป็นพาลินโดรม

ดังนั้น หากอินพุตเป็น s ="xyyx" ผลลัพธ์จะเป็น 3 ตามที่เราแยกเป็น ["x", "yy", "x"], ["x", "y", " y","x"], ["xyyx"].

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

• n :=ขนาดของ s
• ตาราง :=รายการขนาด n + 1 และเติมด้วย 0
• ตาราง[0] :=1
• สำหรับฉันในช่วง 0 ถึง n ให้ทำ
  • สำหรับ j ในช่วง 0 ถึง i - 1 ทำ
    • sub :=s[จากดัชนี j ถึง i]
    • ถ้า sub คือ palindrome แล้ว
      • table[i] :=table[i] + table[j]
• คืนค่าองค์ประกอบสุดท้ายของตาราง

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

ตัวอย่าง

class Solution:
   def solve(self, s):
      n = len(s)
      table = [1] + [0] * n
      for i in range(n + 1):
         for j in range(i):
            sub = s[j:i]
            if sub == sub[::-1]:
               table[i] += table[j]
      return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

อินพุต

"xyyx"

ผลลัพธ์

3