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
  • 对于 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"

输出

3

更新于： 2020年12月2日

285 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告