用Python编写程序查找使得给定的anagram的最小交换次数

假设我们有两个字符串S和T，它们互为anagram。我们需要找到将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
对于范围在i + 1到T大小之间的j，
- 如果x与S[j]相同，则
  - 交换S[i]和S[j]
  - ret：=ret和（1 + util（S，T，i + 1））的最小值
  - 交换S[i]和S[j]
返回ret
从主方法做以下事情：
返回util（S，T，0）

让我们看下面的实现以获得更好的理解 –

更多Python相关文章，请阅读：Python 教程

示例

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