0

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

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

例子：

字符串 = bpdcg

Q = 2

子串：

bz - 得分：2

zd - 得分：5

DM - 得分：7

ng - 分数：10

在此示例中，您可以将字符串中的“p”更改为“z”，将“c”更改为“n”，从而获得最高分数 b。因此，您的新字符串是“bzdng”，其得分为 2+5+10 = 17。

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

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

解决此问题的最佳方法是什么？

4

1 回答 1

1

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

令 L 是开始任何长度为 2 的评分子串的字母集，以及一个特殊字母“*”，它代表除这些之外的任何其他字母。

令 S(i, j, c) 是使用 j 替换的字符串（直到索引 i）中可能的最大分数，其中字符串以字符 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 的评分词的字母才需要尝试。

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

于 2014-10-28T07:57:35.807 回答