Chương trình tìm số lần xóa tối thiểu để tạo chuỗi chuỗi trong Python

Giả sử chúng ta có hai chuỗi chữ thường s và t, bây giờ hãy xem xét một phép toán trong đó chúng ta có thể xóa bất kỳ ký tự nào trong bất kỳ chuỗi nào trong hai chuỗi này. Chúng ta phải tìm số phép toán tối thiểu cần thiết để làm cho s và t bằng nhau.

Vì vậy, nếu đầu vào là s =​​"pipe" t ="nine", thì đầu ra sẽ là 2, vì chúng ta có thể xóa "p" khỏi s và "r" khỏi t để làm cho các chuỗi này giống như "ipe"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=kích thước của s
• n:=kích thước của t
• Định nghĩa một hàm dp (). Điều này sẽ mất tôi, j
• nếu tôi giống với m, thì
  • return n - j
• ngược lại khi j giống với n thì
  • trả lại m - i
• nếu không,
  • nếu s [i] giống với t [j], thì
    • trả về dp (i + 1, j + 1)
  • nếu không,
    • trả về 1 + (tối thiểu là dp (i + 1, j) và dp (i, j + 1))
• Từ phương thức chính, trả về dp (0, 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

"pipe", "ripe"

Đầu ra

2