用 Python 检查两个字符串的编辑距离是 0 还是 1

pythonserver side programmingprogramming更新于 2026/2/2 5:32:17

假设我们有两个字符串 S 和 T，我们必须检查它们是否是 1 还是 0 编辑距离。编辑操作可以定义为删除一个字符、添加一个字符或用另一个字符替换一个字符。

因此，如果输入为 S = "hello", T = "hallo"，则输出将为 True，因为这两个字符串的编辑距离为 1。

为了解决这个问题，我们将遵循以下步骤 −

m := S 的大小，n := T 的大小
i := 0, j := 0
count := 0
if |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))