โปรแกรมตรวจสอบสตริงสามารถแบ่งออกเป็นสามพาลินโดรมหรือไม่ในPython

สมมติว่าเรามีสตริง s เราต้องตรวจสอบว่าเราสามารถแยก s ออกเป็นสามสตริงย่อยพาลินโดรมได้หรือไม่

ดังนั้น หากอินพุตเป็น s ="levelpopracecar" เอาต์พุตจะเป็น True เพราะเราสามารถแยกเป็น "ระดับ" "ป๊อป" "รถแข่ง" ทั้งหมดเป็นพาลินโดรมได้

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

• n :=ขนาดของ s

• dp :=เมทริกซ์ของคำสั่ง n x n และเติมเท็จ

• สำหรับฉันในช่วง n-1 ถึง 0, ลดลง 1 ทำ

  • สำหรับ j ในช่วง 0 ถึง n - 1 ทำ

    • ถ้า i>=j แล้ว

      • dp[i, j] :=จริง

    • มิฉะนั้นเมื่อ s[i] เหมือนกับ s[j] แล้ว

      • dp[i, j] :=dp[i+1, j-1]

  • สำหรับฉันอยู่ในช่วง 1 ถึง n - 1 ทำ

    • สำหรับ j ในช่วง i+1 ถึง n - 1 ทำ

      • ถ้า dp[0, i-1] และ dp[i, j-1] และ dp[j, n-1] ทั้งหมดเป็นจริง ดังนั้น

        • คืนค่า True

• คืนค่าเท็จ

ตัวอย่าง

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

def solve(s):
   n = len(s)

   dp = [[False] * n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(n):
         if i >= j:
            dp[i][j] = True
         elif s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1]
   for i in range(1, n):
      for j in range(i+1, n):
         if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
            return True
   return False

s = "levelpopracecar"
print(solve(s))

อินพุต

"levelpopracecar"

ผลลัพธ์

True