পাইথনে দেওয়া অ্যানাগ্রাম बनाने के लिए न्यूनतम स्वैप की संख्या खोजने का प्रोग्राम

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