Kiểm tra xem khoảng cách chỉnh sửa giữa hai chuỗi có phải là một trong Python hay không

Giả sử chúng ta có hai chuỗi s và t. Chúng ta phải kiểm tra xem khoảng cách chỉnh sửa giữa s và t có chính xác là một hay không. Ở đây, chỉnh sửa giữa hai chuỗi có nghĩa là bất kỳ trong ba chuỗi này -

• Chèn một ký tự
• Xóa một ký tự
• Thay thế một ký tự

Vì vậy, nếu đầu vào là s =​​"hello" t ="heillo", thì đầu ra sẽ là True vì chúng ta cần chèn một ký tự vào s để nhận được t.

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

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

Ví dụ

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

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

Đầu vào

"hello", "heillo"

Đầu ra

True