Chương trình tìm số lần hoán vị tối thiểu để biến chuỗi S thành chuỗi T (anagram) bằng Python

Cho hai chuỗi S và T là anagram của nhau. Nhiệm vụ là tìm số lần hoán vị (swap) tối thiểu trong S để biến nó thành T.

Ví dụ: S = "kolkata", T = "katloka", kết quả là 3 (hoán vị theo trình tự: katloka → kotlaka → koltaka → kolkata).

Giải thuật

Sử dụng đệ quy có quay lui (backtracking):

• Định nghĩa hàm util(S, T, i):
  • Nếu i >= len(S): trả về 0.
  • Nếu S[i] == T[i]: gọi đệ quy util(S, T, i+1).
  • Ngược lại, tìm tất cả vị trí j > i mà S[j] == T[i], hoán vị S[i] và S[j], đệ quy, sau đó hoán vị ngược lại (backtrack). Lấy giá trị nhỏ nhất.
• Từ hàm chính gọi util(S, T, 0).

Ví dụ minh họa

class Solution:
    def util(self, S, T, i):
        S = list(S)
        T = list(T)
        if i >= len(S):
            return 0
        if S[i] == T[i]:
            return self.util(S, T, i + 1)
        x = T[i]
        ret = 99999
        for j in range(i + 1, len(T)):
            if x == S[j]:
                S[i], S[j] = S[j], S[i]
                ret = min(ret, 1 + self.util(S, T, i + 1))
                S[i], S[j] = S[j], S[i]
        return ret

    def solve(self, S, T):
        return self.util(S, T, 0)

ob = Solution()
S = "kolkata"
T = "katloka"
print(ob.solve(S, T))

Đầu vào

"kolkata", "katloka"

Đầu ra

3