在 Python 中，用程序查找删除最多 k 个字符后游程编码的最小长度

pythonserver side programmingprogramming更新于 2025/12/1 3:24:17

假设我们有一个字符串 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, 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))