पायथन में दिए गए विपर्यय बनाने के लिए आवश्यक न्यूनतम स्वैप खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो तार S और T हैं और वे एक दूसरे के आरेख हैं। हमें इसे T के समान बनाने के लिए S में आवश्यक न्यूनतम स्वैप की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट एस ="कोलकाता" टी ="कटलोक" जैसा है, तो आउटपुट 3 होगा, जैसा कि इस क्रम में स्वैप किया जा सकता है [कटलोक (दिया गया), कोटलाका, कोलकाता, कोलकाता]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

उपयोग() फ़ंक्शन को परिभाषित करें। इसमें S, T, i
यदि i>=S का आकार, तो
- वापसी 0
यदि S[i], T[i] के समान है, तो
- रिटर्न यूटिल (एस, टी, आई + 1)
x :=टी[i]
रिट:=99999
j श्रेणी में i + 1 से T के आकार के लिए, करें
- यदि x, S[j] के समान है, तो
  - स्वैप S[i] और S[j]
  - ret :=न्यूनतम रिट और (1 + util(S, T, i + 1))
  - स्वैप S[i] और S[j]
रिटर्न रिटर्न
मुख्य विधि से निम्न कार्य करें:
रिटर्न यूटिल (एस, टी, 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"