Python程式：移除最多k個字元後，求行程長度編碼的最小長度

假設我們有一個字串s和另一個值k。我們可以從s中刪除最多k個字元，使得s的行程長度編碼版本的長度最小。眾所周知，行程長度編碼是一種字串壓縮方法，它將連續相同的字元（2次或更多次）替換為字元和表示字元計數的數字的串聯。例如，如果我們有一個字串“xxyzzz”，那麼我們將“xx”替換為“x2”，將“zzz”替換為“z3”。所以壓縮後的字串現在是“x2yz3”。因此，在這個問題中，我們必須找到在刪除最多k個值後s的行程長度編碼版本的最小長度。

因此，如果輸入類似於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]相同，則

    • 如果l2為1或9，返回f(p-1, k, c, min(10, l2+1)) + 1；否則返回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

更新於：2021年10月6日

165 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始
廣告