Chương trình tìm số lần hoán đổi tối thiểu cần thiết để thực hiện đảo chữ cái đã cho trong python

Giả sử chúng ta có hai chuỗi S và T và chúng là đảo ngữ của nhau. Chúng ta phải tìm số lượng hoán đổi tối thiểu cần thiết trong S để làm cho nó giống như T.

Vì vậy, nếu đầu vào giống như S ="kolkata" T ="katloka", thì đầu ra sẽ là 3, có thể hoán đổi trong chuỗi này [katloka (đã cho), kotlaka, koltaka, kolkata].

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

• Xác định một hàm dùng (). Điều này sẽ mất S, T, i
• if i> =size of S, then
  • trả về 0
• nếu S [i] giống T [i], thì
  • trả về sử dụng (S, T, i + 1)
• x:=T [i]
• ret:=99999
• đối với j trong phạm vi i + 1 đến kích thước của T, thực hiện
  • nếu x giống với S [j], thì
    • hoán đổi S [i] và S [j]
    • ret:=tối thiểu ret và (1 + use (S, T, i + 1))
    • hoán đổi S [i] và S [j]
• trả lời lại
• Từ phương thức chính, hãy làm như sau:
• trả về sử dụng (S, T, 0)

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