পাইথনে প্রদত্ত অ্যানাগ্রাম তৈরি করার জন্য প্রয়োজনীয় ন্যূনতম অদলবদল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং S এবং T আছে এবং তারা একে অপরের অ্যানাগ্রাম। এটিকে T-এর মতো করার জন্য আমাদের S-এ প্রয়োজনীয় ন্যূনতম সংখ্যক অদলবদল খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি S ="kolkata" T ="katloka" এর মত হয়, তাহলে আউটপুট হবে 3, যেমন এই ক্রমটিতে অদলবদল করা যেতে পারে [কাটলোকা (প্রদত্ত), কোটলাকা, কোলতাকা, কোলকাতা]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন util() সংজ্ঞায়িত করুন। এর জন্য S, T, i
যদি i>=S এর আকার হয়, তাহলে
- রিটার্ন 0
যদি S[i] T[i] এর মত হয়, তাহলে
- ইউটিল রিটার্ন (S, T, i + 1)
x :=T[i]
ret :=99999
j রেঞ্জ i + 1 থেকে T এর আকারের জন্য, করুন
- যদি x S[j] এর মত হয়, তাহলে
  - S[i] এবং S[j]
  - ret :=সর্বনিম্ন ret এবং (1 + util(S, T, i + 1))
  - S[i] এবং S[j]
রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
ইউটিল রিটার্ন (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"