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

मान लीजिए हमारे पास दो स्ट्रिंग 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]
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] को वापस स्वैप करें
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"