Python程式：找出使兩個字串相等的最小刪除次數

假設我們有兩個小寫字串 s 和 t，現在考慮一個操作，我們可以刪除這兩個字串中的任意字元。我們必須找到使 s 和 t 相等的所需最小操作次數。

因此，如果輸入類似於 s = "pipe" t = "ripe"，則輸出將為 2，因為我們可以從 s 中刪除 "p"，從 t 中刪除 "r" 以使這兩個字串相同 "ipe"

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

m := s 的長度
n := t 的長度
定義一個函式 dp()。這將接收 i, j
如果 i 等於 m，則
- 返回 n - j
否則，如果 j 等於 n，則
- 返回 m - i
否則，
- 如果 s[i] 等於 t[j]，則
  - 返回 dp(i + 1, j + 1)
- 否則，
  - 返回 1 + (dp(i + 1, j) 和 dp(i, j + 1) 的最小值)
從主方法返回 dp(0, 0)

示例

讓我們看看下面的實現，以便更好地理解：

def solve(s, t):
   m = len(s)
   n = len(t)

   def dp(i, j):
      if i == m:
         return n - j
      elif j == n:
         return m - i
      else:
         if s[i] == t[j]:
            return dp(i + 1, j + 1)
         else:
            return 1 + min(dp(i + 1, j), dp(i, j + 1))
   return dp(0, 0)

s = "pipe"
t = "ripe"
print(solve(s, t))

輸入

"pipe", "ripe"

輸出

Arnab Chakraborty

更新於：2021年10月18日

478 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習