โปรแกรมหาจำนวนการสลับน้อยที่สุดเพื่อทำให้สตริงเป็นอะนาแกรมใน Python

สมมติว่าเรามีสตริงสองตัว S และ T ซึ่งเป็นอะนาแกรมกัน เราต้องการหาจำนวนการสลับน้อยที่สุดใน S เพื่อให้มันเหมือนกับ T

เช่น ถ้าอินพุตเป็น S = "kolkata" T = "katloka" ผลลัพธ์จะเป็น 3 เนื่องจากสามารถสลับได้ในลำดับ [katloka (given), kotlaka, koltaka, kolkata]

ขั้นตอนการแก้ปัญหา

• กำหนดฟังก์ชัน util() รับ S, T, i
• ถ้า i >= len(S) คืนค่า 0
• ถ้า S[i] == T[i] คืนค่า util(S, T, i + 1)
• x := T[i]
• ret := 99999
• วนลูป j จาก i + 1 ถึงขนาดของ T:
  • ถ้า x == S[j]:
    • สลับ S[i] และ S[j]
    • ret := min(ret, 1 + util(S, T, i + 1))
    • สลับกลับ S[i] และ S[j]
• คืนค่า ret
• จากเมธอดหลัก เรียก util(S, T, 0)

ตัวอย่างโค้ด

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

อินพุต

"kolkata", "katloka"

เอาต์พุต

3