Chương trình kiểm tra hai chuỗi có 0 hoặc 1 khoảng cách chỉnh sửa hay không trong Python

Giả sử chúng ta có hai chuỗi S và T, chúng ta phải kiểm tra xem chúng có cách nhau một hay không khoảng cách chỉnh sửa hay không. Thao tác chỉnh sửa có thể được định nghĩa là xóa một ký tự, thêm một ký tự hoặc thay thế một ký tự bằng một ký tự khác.

Vì vậy, nếu đầu vào giống như S ="hello", T ="hallo", thì đầu ra sẽ là True, vì hai chuỗi này có khoảng cách chỉnh sửa là 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=kích thước của S, n:=kích thước của T
• i:=0, j:=0
• số lượng:=0
• nếu | m - n |> 1, sau đó
  • trả về Sai
• while i
• nếu S [i] không giống T [j], thì
  • nếu số đếm giống như 1, thì
    • trả về Sai
  • nếu m
  • j:=j + 1
• ngược lại khi m> n, thì
  • i:=i + 1
• nếu không,
  • i:=i + 1, j:=j + 1
• count:=count + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

"hello", "hallo"

Đầu ra

True