Chương trình tìm độ dài nhỏ nhất của mã hóa độ dài chạy (RLE) có mất mát bằng Python

Cho chuỗi chữ thường s và số k. Có thể xóa bất kỳ k ký tự liên tiếp nào, sau đó mã hóa độ dài chạy (run-length encoding). Tìm độ dài mã hóa nhỏ nhất có thể.

Ví dụ: s = "xxxxxyyxxxxxzzxxx", k = 2 → 6 (xóa "zz" cho "5x2y8x" độ dài 6).

Quy trình giải quyết

1. Hàm calc_cost(l): chi phí mã hóa độ dài l (0→0, 1→1, khác→len(str(l))+1).
2. Hàm prefix(s): tính mảng tiền tố lưu chi phí mã hóa và độ dài run hiện tại.
3. Tính pre cho s và suf cho s[::-1].
4. Duyệt mọi vị trí xóa k ký tự liên tiếp, kết hợp pre và suf tính chi phí.
5. Trả về chi phí nhỏ nhất.

Ví dụ mã nguồn

def calc_cost(l):
    if l == 0:
        return 0
    if l == 1:
        return 1
    else:
        return len(str(l)) + 1

class Solution:
    def solve(self, s, k):
        def prefix(s):
            pre = [[0, 0]]
            last = None
            for c in s:
                if c == last:
                    pre.append([pre[-1][0], pre[-1][1] + 1])
                else:
                    pre.append([pre[-1][0] + calc_cost(pre[-1][1]), 1])
                last = c
            return pre
        pre = prefix(s)
        suf = prefix(s[::-1])[::-1]
        ans = float("inf")
        for i in range(len(s) - k + 1):
            j = i + k
            left, midl = pre[i]
            right, midr = suf[j]
            cost = left + right
            c1 = s[i - 1] if i > 0 else None
            c2 = s[j] if j < len(s) else None
            if c1 == c2:
                cost += calc_cost(midl + midr)
            else:
                cost += calc_cost(midl) + calc_cost(midr)
            ans = min(ans, cost)
        return ans

ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))  # Output: 6

Đầu vào

s = "xxxxxyyxxxxxzzxxx"

Đầu ra

6