假设我们有一个字符串 s 和另一个值 k。我们最多可以从 s 中删除 k 个字符,使得 s 的游程编码版本的长度最小。众所周知,行程编码是一种字符串压缩方法,它用字符和标记字符计数的数字的串联替换连续的相同字符(2 次或更多次)。例如,如果我们有一个字符串“xxyzzz”,那么我们用“x2”替换“xx”,用“z3”替换“zzz”。所以压缩的字符串现在是“x2yz3”。所以在这个问题中,我们必须在删除最多 k 个值后找到 s 的游程编码版本的最小长度。
所以,如果输入像 s = "xxxyzzzw", k = 2,那么输出将是 4,因为字符串 s 没有删除任何东西,游程编码是 "x3yz3w" 长度 6。如果我们删除两个字符并使 s像“xzzzw”或“xyzzz”那么压缩版本将是“xz3w”,“xyz3”的长度都是4。
让我们看下面的实现来更好地理解
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