Chương trình tìm độ dài tối thiểu của mã hóa độ dài chạy sau khi xóa tối đa k ký tự trong Python

Giả sử chúng ta có một chuỗi s và một giá trị khác k. Chúng ta có thể xóa tối đa k ký tự khỏi s sao cho độ dài của phiên bản mã hóa độ dài chạy của s là nhỏ nhất. Như chúng ta biết mã hóa độ dài chạy là một phương pháp nén chuỗi thay thế các ký tự giống nhau liên tiếp (2 hoặc nhiều lần) bằng cách ghép ký tự và số đánh dấu số ký tự. Ví dụ, nếu chúng ta có một chuỗi "xxyzzz" thì chúng ta thay thế "xx" bằng "x2" và thay thế "zzz" bằng "z3". Vì vậy, chuỗi nén bây giờ là "x2yz3". Vì vậy, trong bài toán này, chúng ta phải tìm độ dài tối thiểu của phiên bản mã hóa độ dài chạy của s sau khi xóa nhiều nhất k giá trị.

Vì vậy, nếu đầu vào là s =​​"xxxyzzzw", k =2, thì đầu ra sẽ là 4 vì chuỗi s mà không xóa bất kỳ thứ gì thì mã hóa độ dài chạy là "x3yz3w" dài 6. Nếu chúng ta loại bỏ hai ký tự và tạo s như "xzzzw" hoặc "xyzzz" thì các phiên bản nén sẽ là "xz3w", "xyz3" đều có độ dài là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu k> =kích thước của s, thì

  • trả về 0

• nếu kích thước của s là 100 và tất cả các ký tự trong s đều giống nhau thì

  • nếu k giống 0 thì

    • trả về 4

  • nếu k <=90, thì

    • trả về 3

  • nếu k <=98, thì

    • trả lại 2

• trả lại 1

• Xác định một hàm f (). Điều này sẽ mất p, k, c, l2

• nếu k <0, thì

  • trả lại 10000

• nếu p <0, thì

  • trả về 0

• nếu c giống với s [p] thì

  • trả về f (p-1, k, c, tối thiểu là 10 và l2 + 1) + 1 nếu l2 là 1 hoặc 9 nếu không thì 0

• nếu không,

  • trả về tối thiểu f (p-1, k-1, c, l2), f (p-1, k, s [p], 1) + 1

• Từ phương thức chính trả về f (kích thước của s -1, k, null, 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

def solve(s, k):
   if k >= len(s):
      return 0
   if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])):
      if k == 0:
         return 4
      if k <= 90:
         return 3
      if k <= 98:
         return 2
         return 1

   def f(p, k, c, l2):
      if k < 0:
         return 10000
      if p < 0:
         return 0
      if c == s[p]:
         return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
      else:
         return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)

   return f(len(s)-1, k, None, 0)

s = "xxxyzzzw"
k = 2
print(solve(s, k))

Đầu vào

"xxxyzzzw", 2

Đầu ra

4