程序查找在python中进行给定字谜所需的最小交换

假设我们有两个字符串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

• 对于范围i + 1至T大小的j，

• 交换S [i]和S [j]

• ret：= ret的最小值和（1 + util（S，T，i + 1））

• 交换S [i]和S [j]

• 如果x与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"

输出结果

3