โปรแกรมหาจำนวนพาลินโดรมที่เป็นไปได้ที่เราสามารถทำได้โดยการตัดแต่งสตริงใน Python

สมมติว่าเรามีสตริง s เราต้องหาจำนวนวิธีที่เราจะได้พาลินโดรมโดยการตัดด้านซ้ายและด้านขวาของ s

ดังนั้น หากอินพุตเป็น s ="momo" ผลลัพธ์จะเป็น 6 ดังที่คุณจะได้รับ ["mom", "omo", "o", "o", "m", "m", " o")

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

• กำหนดฟังก์ชัน expand() นี่จะใช้เวลา i, j, s

• ค :=0

• ในขณะที่ i>=0 และ j <ขนาดของ s และ s[i] เท่ากับ s[j] ให้ทำ

  • ผม :=ผม − 1, j :=j + 1

  • ค :=ค + 1

• กลับค

• จากวิธีหลัก ให้ทำดังนี้

• ค :=0

• สำหรับฉันในช่วง 0 ถึงขนาด s ทำ

  • c :=c + ขยาย (i, i, s)

  • c :=c + expand(i, i + 1, s)

• กลับค

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

ตัวอย่าง

def expand(i, j, s):
   c = 0
   while i >= 0 and j < len(s) and s[i] == s[j]:
      i −= 1
      j += 1
      c += 1
   return c
class Solution:
   def solve(self, s):
      c = 0
      for i in range(len(s)):
         c += expand(i, i, s)
         c += expand(i, i + 1, s)
      return c
ob = Solution()
s = "momo"
print(ob.solve(s))

อินพุต

"momo"

ผลลัพธ์

6