使用Python查找删除最多k个字符后的最小运行长度编码长度的程序

使用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, 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程