ตรวจสอบว่าแก้ไขระยะทางระหว่างสองสายเป็นหนึ่งใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องตรวจสอบว่าระยะการแก้ไขระหว่าง s และ t เป็นหนึ่งเดียวหรือไม่ การแก้ไขระหว่างสองสตริงหมายถึงหนึ่งในสามนี้ -

• ใส่อักขระ
• ลบอักขระ
• แทนที่อักขระ

ดังนั้น หากอินพุตเป็น s ="hello" t ="heillo" ผลลัพธ์จะเป็น True เนื่องจากเราต้องแทรกอักขระหนึ่งตัวลงใน s เพื่อให้ได้ t

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า |ขนาด s - ขนาดของ t|> 1 แล้วก็
  • คืนค่าเท็จ
• edit_dist_cnt :=0, i :=0, j :=0
• ในขณะที่ฉัน <ขนาดของ s และ j <ขนาดของ t ทำ
  • ถ้า s[i] ไม่เหมือนกับ t[j] แล้ว
    • ถ้า edit_dist_cnt เหมือนกับ 1 แล้ว
      • คืนค่าเท็จ
    • ถ้าขนาดของ s> ขนาดของ t แล้ว
      • ผม :=ผม + 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
• ถ้าฉัน <ขนาดของ s หรือ j <ขนาดของ t แล้ว
  • edit_dist_cnt :=edit_dist_cnt + 1
• คืนค่า จริง เมื่อ edit_dist_cnt เหมือนกับ 1 มิฉะนั้น จะเป็นเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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