Giả sử chúng ta có một chuỗi chữ thường s và một giá trị khác k. Bây giờ hãy xem xét một hoạt động mà chúng ta thực hiện mã hóa độ dài chạy trên một chuỗi bằng cách đặt các ký tự liên tiếp lặp lại làm số lượng và ký tự. Vì vậy, nếu chuỗi giống như "aaabbc" sẽ được mã hóa thành "3a2bc". Ở đây chúng tôi không đặt "1c" cho "c" vì nó chỉ xuất hiện một lần liên tiếp. Vì vậy, trước tiên chúng ta có thể xóa bất kỳ ký tự liên tiếp nào trong s, sau đó tìm độ dài tối thiểu có thể có của mã chạy-dài mã kết quả.
Vì vậy, nếu đầu vào giống như s ="xxxxxyyxxxxxzzxxx", k =2, thì đầu ra sẽ là 6, vì hai lựa chọn rõ ràng là loại bỏ "yy" hoặc "zz". Nếu chúng ta loại bỏ "yy" s, thì chúng ta sẽ nhận được "10x2z3x" có chiều dài là 7. Nếu chúng ta loại bỏ "zz" s, thì sẽ nhận được "5x2y8x" có độ dài là 6, đây là nhỏ nhất.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm calc_cost (). Điều này sẽ mất l
-
nếu l giống 0 thì
-
trả về 0
-
-
nếu l giống với 1, thì
-
trả lại 1
-
-
nếu không,
-
kích thước trả về của str (l) + 1
-
-
Xác định tiền tố hàm (). Điều này sẽ mất s
-
pre:=một danh sách ban đầu có cặp [0, 0]
-
cuối cùng:=null
-
đối với mỗi c trong s, thực hiện
-
nếu c giống với cuối cùng thì
-
chèn một cặp (phần tử thứ 0 của mục cuối cùng của trước, 1 + phần tử thứ nhất của mục cuối cùng của trước) vào trước
-
-
nếu không,
-
insert (phần tử thứ 0 của mục cuối cùng của trước) + calc_cost (phần tử đầu tiên của mục cuối cùng của trước, 1) vào trước
-
-
cuối cùng:=c
-
-
trả lại trước
-
-
Từ phương thức chính, thực hiện như sau:
-
pre:=prefix (s)
-
suf:=đảo ngược tiền tố (các thứ tự ngược lại)
-
ans:=infinity
-
đối với tôi trong phạm vi từ 0 đến kích thước của s - k + 1, thực hiện
-
j:=i + k
-
cặp (trái, giữa):=pre [i]
-
cặp (phải, giữa):=suf [j]
-
chi phí:=left + right
-
c1:=s [i - 1] nếu i> 0 nếu không thì null
-
c2:=s [j] nếu j
-
nếu c1 giống với c2 thì
-
cost:=cost + calc_cost (midl + midr)
-
-
nếu không,
-
cost:=cost + calc_cost (midl) + calc_cost (midr)
-
-
ans:=tối thiểu ans và chi phí
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)) Đầu vào
s = "xxxxxyyxxxxxzzxxx"
Đầu ra
6