โปรแกรมค้นหาการลบขั้นต่ำเพื่อสร้างสตริงสตริงใน Python

สมมติว่าเรามีสตริงตัวพิมพ์เล็กสองตัว s และ t ตอนนี้ให้พิจารณาการดำเนินการที่เราสามารถลบอักขระใดๆ ในสองสตริงนี้ได้ เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นในการทำให้ s และ t เท่ากัน

ดังนั้น หากอินพุตเป็น s ="pipe" t ="ripe" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถลบ "p" ออกจาก s และ "r" จาก t เพื่อทำให้สตริงเหล่านี้เป็น "ipe"

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

• m :=ขนาดของ s
• n :=ขนาดของ t
• กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j
• ถ้าฉันเหมือนกับ m แล้ว
  • กลับ n - j
• มิฉะนั้นเมื่อ j เหมือนกับ n แล้ว
  • ส่งคืน m - i
• มิฉะนั้น
  • ถ้า s[i] เหมือนกับ t[j] แล้ว
    • ผลตอบแทน dp(i + 1, j + 1)
  • มิฉะนั้น
    • คืนค่า 1 + (ขั้นต่ำของ dp(i + 1, j) และ dp(i, j + 1))
• จากวิธีหลัก ให้คืนค่า dp(0, 0)

ตัวอย่าง

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

def solve(s, t):
   m = len(s)
   n = len(t)

   def dp(i, j):
      if i == m:
         return n - j
      elif j == n:
         return m - i
      else:
         if s[i] == t[j]:
            return dp(i + 1, j + 1)
         else:
            return 1 + min(dp(i + 1, j), dp(i, j + 1))
   return dp(0, 0)

s = "pipe"
t = "ripe"
print(solve(s, t))

อินพุต

"pipe", "ripe"

ผลลัพธ์

2