Python程式：檢查兩個字串的編輯距離是否為0或1

假設我們有兩個字串S和T，我們需要檢查它們的編輯距離是否為零或一。編輯操作可以定義為刪除一個字元、新增一個字元或用另一個字元替換一個字元。

因此，如果輸入類似於S = "hello"，T = "hallo"，則輸出將為True，因為這兩個字串的編輯距離為1。

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

  • m := S的長度，n := T的長度
  • i := 0，j := 0
  • count := 0
  • 如果 |m - n| > 1，則
    • 返回 False
  • 當 i < m 且 j < n 時，執行以下操作：
    • 如果 S[i] 不等於 T[j]，則
      • 如果 count 等於 1，則
        • 返回 False
      • 如果 m < n，則
        • j := j + 1
      • 否則，如果 m > n，則
        • i := i + 1
      • 否則，
        • i := i + 1，j := j + 1
      • count := count + 1
    • 否則，
      • i := i + 1，j := j + 1
  • 返回 True

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

示例

 線上演示

class Solution:
   def solve(self, S, T):
      m, n = len(S), len(T)
      i, j = 0, 0
      count = 0
      if abs(m - n) > 1:
         return False
      while i < m and j < n:
         if S[i] != T[j]:
            if count == 1:
               return False
            if m < n:
               j += 1
            elif m > n:
               i += 1
            else:
               i += 1
               j += 1
            count += 1
         else:
            i += 1
            j += 1
      return True
ob = Solution()
S = "hello"
T = "hallo"
print(ob.solve(S, T))

輸入

"hello", "hallo"

輸出

True

更新於：2020年10月19日

瀏覽量：337

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告