โปรแกรมนับการดำเนินการน้อยสุดทำให้สตริงเป็นการต่อสตริงเดียวกันสองครั้งใน Python

คำอธิบายปัญหา

กำหนดสตริง s อนุญาต: ลบ, แทรก, แก้ไข ตัวอักษร หาจำนวนการดำเนินการน้อยที่สุด เพื่อให้ s = t + t สำหรับสตริง t ใดๆ

ตัวอย่าง

s = "pqrxqsr" → Output: 2

แก้ 'x'→'p', ลบ 's' ได้ "pqrpqr" = "pqr" + "pqr"

ขั้นตอนการแก้ปัญหา (Edit Distance)

1. ลองทุกจุดตัด i แบ่ง s เป็น s[:i] และ s[i:]
2. คำนวณ edit_distance(s[:i], s[i:]) (Levenshtein distance)
3. หาค่า min ทุก i

การตนการทำงาน (Python)

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))  # Output: 2

อินพุต / เอาต์พุต

Input:  "pqrxqsr"
Output: 2