โปรแกรมค้นหาความยาวขั้นต่ำของการเข้ารหัสความยาวรันหลังจากลบอักขระไม่เกิน k ตัวใน Python

สมมติว่าเรามีสตริง s และอีกค่าหนึ่งคือ k เราสามารถลบอักขระได้ไม่เกิน k ตัวจาก s เพื่อให้ความยาวของเวอร์ชันที่เข้ารหัสของ s มีความยาวน้อยที่สุด อย่างที่เราทราบดีว่าการเข้ารหัสตามความยาวของรันเป็นวิธีการบีบอัดสตริงที่แทนที่อักขระที่เหมือนกันต่อเนื่องกัน (2 ครั้งขึ้นไป) ด้วยการต่ออักขระและตัวเลขที่ทำเครื่องหมายการนับของอักขระ ตัวอย่างเช่น หากเรามีสตริง "xxyzzz" เราจะแทนที่ "xx" ด้วย "x2" และแทนที่ "zzz" ด้วย "z3" ดังนั้นสตริงที่บีบอัดจึงเป็น "x2yz3" ดังนั้นในปัญหานี้ เราต้องหาความยาวขั้นต่ำของเวอร์ชันเข้ารหัสความยาวรันหลังจากลบค่า k มากที่สุด

ดังนั้น หากอินพุตเป็น s ="xxxyzzzw", k =2 เอาต์พุตจะเป็น 4 เนื่องจากสตริง s ไม่ได้ลบอะไรเลย การเข้ารหัสความยาวรันจะเป็น "x3yz3w" ความยาว 6 หากเราลบอักขระสองตัวและทำให้ s เช่น "xzzzw" หรือ "xyzzz" ดังนั้นเวอร์ชันที่บีบอัดจะเป็น "xz3w", "xyz3" ทั้งคู่มีความยาว 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า k>=ขนาดของ s แล้ว

  • คืนค่า 0

• หากขนาดของ s คือ 100 และอักขระทั้งหมดใน s เท่ากัน

  • ถ้า k เท่ากับ 0 แล้ว

    • กลับ 4

  • ถ้า k <=90 แล้ว

    • กลับ 3

  • ถ้า k <=98 แล้ว

    • กลับ 2

• กลับ 1

• กำหนดฟังก์ชัน f() นี่จะใช้เวลา p, k, c, l2

• ถ้า k <0 แล้ว

  • ผลตอบแทน 10000

• ถ้า p <0 แล้ว

  • คืนค่า 0

• ถ้า c เหมือนกับ s[p] แล้ว

  • คืนค่า f(p-1, k, c, ขั้นต่ำ 10 และ l2+1) + 1 ถ้า l2 เป็น 1 หรือ 9 มิฉะนั้น 0

• มิฉะนั้น

  • ส่งกลับขั้นต่ำของ f(p-1, k-1, c, l2) , f(p-1, k, s[p], 1) + 1

• จากวิธีหลักส่งคืน f(ขนาดของ s -1, k, null, 0)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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))

อินพุต

"xxxyzzzw", 2

ผลลัพธ์

4