Chương trình biến đổi chuỗi bằng cách lấy ký tự đầu/cuối và chèn lại trong Python

Cho hai chuỗi S và T là hoán vị của nhau. Mỗi phép toán: lấy ký tự đầu hoặc cuối của S và chèn vào vị trí bất kỳ. Tìm số phép toán tối thiểu để biến S thành T.

Ví dụ

Đầu vào: s = "zyvxw", t = "vwxyz".
Đầu ra: 3 (các bước: lấy 'w' chèn sau 'v', lấy 'z' chèn sau 'x', lấy 'y' chèn sau 'x').

Thuật toán

1. Khởi tạo ans = n = len(s).
2. Với mỗi i từ 0 đến n-1:
   • Đặt k = 0.
   • Với j từ i đến n-1:
     • Tìm k trong t sao cho s[j] == t[k].
     • Cập nhật ans = min(ans, n - (j - i + 1)).
     • Tăng k.
3. Trả về ans.

Mã nguồn Python

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 / Đầu ra

Input: "zyvxw", "vwxyz"
Output: 5