Chương trình tạo mục tiêu bằng cách xóa từ đầu tiên hoặc cuối cùng và chèn lại bằng Python

Giả sử chúng ta có hai chuỗi S và T và chúng là hoán vị của nhau. Giả sử có một phép toán mà chúng ta loại bỏ ký tự đầu tiên hoặc ký tự cuối cùng trong S và chèn nó vào bất kỳ vị trí nào trong chuỗi. Sau đó, tìm số phép toán tối thiểu cần thiết để chuyển đổi S thành T.

Vì vậy, nếu đầu vào giống như s ="zyvxw" t ="vwxyz", thì đầu ra sẽ là 3, như các hoạt động sau:Xóa "w" và chèn nó sau "v" để nhận "zyvwx" Xóa "z" và chèn nó sau "x" để lấy "yvwxz" Xóa "y" và chèn nó sau "x" để có "vwxyz".

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

• ans:=size of s, n:=size of s

• đối với tôi trong phạm vi từ 0 đến n-1, hãy thực hiện

  • k:=0

  • đối với j trong phạm vi i đến n-1, thực hiện

    • đối với k trong phạm vi k đến kích thước của t, thực hiện

      • nếu s [j] giống với t [k] thì

        • ans:=tối thiểu ans và n - (j - i + 1)

        • đi ra từ vòng lặp

    • k:=k + 1

  • trả lại ans

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

Ví dụ

class Solution:
   def solve(self, s, t):
      ans = n = len(s)

      for i in range(n):
         k = 0
         for j in range(i, n):
            for k in range(k, len(t)):
               if s[j] == t[k]:
                  ans = min(ans, n - (j - i + 1))
                  break
            k += 1

      return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

Đầu vào

"zyvxw", "vwxyz"

Đầu ra

5