สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s ตอนนี้ให้พิจารณาการดำเนินการ ซึ่งเราสามารถลบ แทรก หรืออัปเดตอักขระใดก็ได้ใน s เราต้องนับจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการสร้าง s =(t concatenate t) สำหรับสตริง t ใดๆ
ดังนั้น หากอินพุตเป็น s ="pqrxqsr" ผลลัพธ์จะเป็น 2 เพราะเราสามารถอัปเดต "x" ด้วย "p" และลบ "s" ดังนั้น s คือ "pqrpqr" นี่คือ s =t ต่อ t สำหรับ t ="pqr"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน edit_distance() นี่จะใช้เวลา s1, s2
- ม :=ขนาดของ s1
- n :=ขนาดของ s2
- cur :=รายการใหม่จากช่วง 0 ถึง n
- สำหรับฉันในช่วง 0 ถึง m - 1 ทำ
- ก่อนหน้า :=cur
- cur :=รายการที่มี (i + 1) และ n จำนวน 0s
- สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
- cur[j + 1] :=prev[j] ถ้า s1[i] และ s2[j] เหมือนกันไม่เช่นนั้น (ค่าต่ำสุดของ cur[j], prev[j], prev[j + 1]) + 1
- ผลตอบแทนเคอร์[n]
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- res :=ขนาดของ s
- สำหรับฉันในช่วง 0 ถึงขนาด s - 1 ทำ
- res :=ขั้นต่ำของ edit_distance (สตริงย่อยของ s จากดัชนี 0 ถึง i - 1, สตริงย่อยของ s จากดัชนี i ถึงปลาย) และ res
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(s): def edit_distance(s1, s2): m, n = len(s1), len(s2) cur = list(range(n + 1)) for i in range(m): prev, cur = cur, [i + 1] + [0] * n for j in range(n): cur[j + 1] = (prev[j] if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1) return cur[n] res = len(s) for i in range(len(s)): res = min(edit_distance(s[:i], s[i:]), res) return res s = "pqrxqsr" print(solve(s))
อินพุต
"pqrxqsr"
ผลลัพธ์
None
