在 Python 中檢查兩個字串之間的編輯距離是否為 1

假設我們有兩個字串 s 和 t。我們需要檢查 s 和 t 之間的編輯距離是否正好為 1。這裡兩個字串之間的編輯是指以下三種情況中的任何一種：

• 插入一個字元
• 刪除一個字元
• 替換一個字元

因此，如果輸入類似於 s = "hello" t = "heillo"，則輸出將為 True，因為我們需要在 s 中插入一個字元才能得到 t。

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

• 如果 |s 的大小 - t 的大小| > 1，則
  • 返回 false
• edit_dist_cnt := 0，i := 0，j := 0
• 當 i < s 的大小 且 j < t 的大小 時，執行以下操作：
  • 如果 s[i] 與 t[j] 不相同，則
    • 如果 edit_dist_cnt 等於 1，則
      • 返回 false
    • 如果 s 的大小 > t 的大小，則
      • i := i + 1
    • 否則，如果 s 的大小 < t 的大小，則
      • j := j + 1
    • 否則，
      • i := i + 1，j := j + 1
    • edit_dist_cnt := edit_dist_cnt + 1
  • 否則，
    • i := i + 1，j := j + 1
• 如果 i < s 的大小 或 j < t 的大小，則
  • edit_dist_cnt := edit_dist_cnt + 1
• 當 edit_dist_cnt 等於 1 時返回 true，否則返回 false

示例

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

 現場演示

def solve(s, t):
   if abs(len(s) - len(t)) > 1:
      return false
   edit_dist_cnt = 0
   i = 0
   j = 0
   while i < len(s) and j < len(t):
      if s[i] != t[j]:
         if edit_dist_cnt == 1:
            return false
         if len(s) > len(t):
            i += 1
         elif len(s) < len(t):
            j += 1
         else:
            i += 1
            j += 1
         edit_dist_cnt +=1
      else:
         i += 1
         j += 1
   if i < len(s) or j < len(t):
      edit_dist_cnt += 1
   return edit_dist_cnt == 1
s = "hello"
t = "heillo"
print(solve(s, t))

輸入

"hello", "heillo"

輸出

True

Arnab Chakraborty

更新於: 2021年1月18日

113 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習