โปรแกรมตรวจสอบสองสายคือ 0 หรือ 1 แก้ไขระยะทางหรือไม่ในPython

สมมติว่าเรามีสองสาย S และ T เราต้องตรวจสอบว่ามีระยะการแก้ไขหนึ่งหรือศูนย์หรือไม่ การดำเนินการแก้ไขสามารถกำหนดเป็นการลบอักขระ การเพิ่มอักขระ หรือการแทนที่อักขระด้วยอักขระอื่น

ดังนั้น หากอินพุตเป็น S ="hello", T ="hallo" ผลลัพธ์จะเป็น True เนื่องจากทั้งสองสตริงมีระยะการแก้ไขเท่ากับ 1

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

• m :=ขนาดของ S, n :=ขนาดของ T
• i :=0, j :=0
• นับ :=0
• ถ้า |m - n|> 1 แล้วก็
  • คืนค่าเท็จ
• ในขณะที่ฉัน
• ถ้า S[i] ไม่เหมือนกับ T[j] แล้ว
  • ถ้านับเท่ากับ 1 แล้ว
    • คืนค่าเท็จ
  • ถ้า ม
  • j :=j + 1
• มิฉะนั้นเมื่อ m> n แล้ว
  • ผม :=ผม + 1
• มิฉะนั้น
  • i :=i + 1, j :=j + 1
• นับ :=นับ + 1

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

ตัวอย่าง

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

อินพุต

"hello", "hallo"

ผลลัพธ์

True