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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告