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)

示例

让我们看看下面的实现以获得更好的理解

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

4

更新于：2021年10月6日

165 次浏览

启动你的职业生涯

完成课程获得认证

开始
广告