Python程式：計算將字串轉換為相同字串兩次連線所需的運算次數

假設我們有一個小寫字串 s。現在考慮一個操作，我們可以刪除、插入或更新 s 中的任何字元。我們需要計算將 s 轉換為 (t 連線 t) 所需的最少操作次數，其中 t 是任何字串。

因此，如果輸入類似於 s = "pqrxqsr"，則輸出將為 2，因為我們可以將 "x" 更新為 "p" 並刪除 "s"，然後 s 為 "pqrpqr"，即 s = t 連線 t，其中 t = "pqr"。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 edit_distance()。它將接收 s1 和 s2 作為引數。
  • m := s1 的大小
  • n := s2 的大小
  • cur := 從 0 到 n 的一個新列表
  • 對於範圍從 0 到 m - 1 的 i，執行以下操作：
    • prev := cur
    • cur := 一個包含 (i + 1) 和 n 個 0 的列表
    • 對於範圍從 0 到 n - 1 的 j，執行以下操作：
      • 如果 s1[i] 和 s2[j] 相同，則 cur[j + 1] := prev[j]，否則 cur[j + 1] := (cur[j]，prev[j]，prev[j + 1] 中的最小值) + 1
  • 返回 cur[n]
  • 從主方法中執行以下操作：
  • res := s 的大小
  • 對於範圍從 0 到 s 的大小 - 1 的 i，執行以下操作：
    • res := edit_distance(s 從索引 0 到 i - 1 的子字串，s 從索引 i 到末尾的子字串) 和 res 中的最小值
  • 返回 res

示例

讓我們看看以下實現以獲得更好的理解：

def solve(s):
   def edit_distance(s1, s2):
      m, n = len(s1), len(s2)
      cur = list(range(n + 1))
      for i in range(m):
         prev, cur = cur, [i + 1] + [0] * n
         for j in range(n):
            cur[j + 1] = (prev[j]
            if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1)
         return cur[n]

   res = len(s)
   for i in range(len(s)):
      res = min(edit_distance(s[:i], s[i:]), res)
   return res

s = "pqrxqsr"
print(solve(s))

輸入

"pqrxqsr"

輸出

None

更新於: 2021年10月18日

136 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告