更改字符串的字母以获得最高分数

Question

给出一个字符串，并且可以在字符串中更改至多Q个字母。您还会得到一个子字符串列表（每两个字符长），并带有相应的分数。字符串中的每个子字符串都会增加总分数。可获得的最高分数是多少？更改字符串的字母以获得最高分数

字符串长度< = 150，Q < = 100，子串<总数= 700

---

实施例：

字符串= bpdcg

Q = 2个

子串：

BZ - 得分：2

ZD - 得分：5

DM - 得分：7

纳克 - 分数：10

在这个例子中，可以实现的最大得分b更改“字符串中的“p”改为“z”，“c”改为“n”。因此，新的字符串为“bzdng”，它的得分为2 + 5 + 10 = 17

我知道，鉴于已经有字母改为一个字符串，比分可以在线性时间使用检查字典匹配算法，如aho-corasick（或复杂程度稍差的Rabin Karp）。但是，尝试每两个字母替换将花费太长时间，然后检查将花费太长时间。

我认为是向后工作，从给定的子构建理想的字符串，然后检查是否相差从原始字符串最多两个字符另一种可能的方法。但是，我不确定如何做到这一点，即使可以完成，我认为这也需要很长时间。

什么是最好的方式去做这件事？

Answer 1

解决这个的有效方法是使用动态规划。

设L的一套启动任何长度为2的得分子的信件，和一个特殊的字母“*”，这表示这些比任何其他字母。

令S（I，J，C）是该串中的最大可能得分（高达索引i）使用j个取代，其中该字符串以字符c的端部（其中，c为L）。

递推关系是有点乱（或至少，我没有发现他们的一个特别美丽的制剂），但这里的一些计算得分最高可能的代码：

infinity = 100000000 

def S1(L1, L2, s, i, j, c, scores, cache): 
    key = (i, j, c) 
    if key not in cache: 
     if i == 0: 
      if c != '*' and s[0] != c: 
       v = 0 if j >= 1 else -infinity 
      else: 
       v = 0 if j >= 0 else -infinity 
     else: 
      v = -infinity 
      for d in L1: 
       for c2 in [c] if c != '*' else L2 + s[i]: 
        jdiff = 1 if s[i] != c2 else 0 
        score = S1(L1, L2, s, i-1, j-jdiff, d, scores, cache) 
        score += scores.get(d+c2 , 0) 
        v = max(v, score) 
     cache[key] = v 
    return cache[key] 

def S(s, Q, scores): 
    L1 = ''.join(sorted(set(w[0] for w in scores))) + '*' 
    L2 = ''.join(sorted(set(w[1] for w in scores))) 
    return S1(L1, L2, s + '.', len(s), Q, '.', scores, {}) 

print S('bpdcg', 2, {'bz': 2, 'zd': 5, 'dm': 7, 'ng': 10}) 

有一些空间优化：

如果j为负

• 计算不提前终止
• 作出选择时，L2的每一个值尝试，而只有字母，可以完成从d得分字需要尝试ING。

总体而言，如果评分词中有k个不同的字母，则算法运行时间为O（QN * k^2）。通过上面的第二次优化，可以将其减少到O（QNw），其中w是计分单词的数量。