程序查找在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