在 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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习