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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以上是 程序查找在python中进行给定字谜所需的最小交换 的全部内容， 来源链接： utcz.com/z/334688.html

回到顶部