โปรแกรมค้นหาสวอปขั้นต่ำที่จำเป็นในการสร้างแอนนาแกรมใน python

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

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา S, T, i
• ถ้า i>=ขนาดของ S แล้ว
  • คืน 0
• ถ้า S[i] เหมือนกับ T[i] แล้ว
  • ผลตอบแทน util(S, T, i + 1)
• x :=T[i]
• ยกเลิก :=99999
• สำหรับ j ในช่วง i + 1 ถึงขนาด T ให้ทำ
  • ถ้า x เหมือนกับ S[j] แล้ว
    • สลับ S[i] และ S[j]
    • ret :=ขั้นต่ำของ ret และ (1 + util(S, T, i + 1))
    • สลับ S[i] และ S[j]
• คืนสินค้า
• จากวิธีหลัก ให้ทำดังนี้:
• ผลตอบแทน 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