更改字符串的字母以獲得最高分數

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是計分單詞的數量。