不规则表达式

Question

我有字典。在

dict = {"fe": 1, "je": 2, "jee": 3, "ain": 3, "dai": 5, "ne": 2, "ai": 2}

任何不在字典中创建单词的字符都是负1分

示例：fejeain - 1+2+3 = 6 feje**b**ain - 1+2-**1**+3 = 5

这是我的绳子

^{pr2}$

我想对一个词的个别部分给予分数。他们的总和就是结果。在

但计算结果有几种方法：

fe-ai-ne-ai = 1+2+2+2=7
fe-ain-e-ai = 1+3-1+2=5

有什么算法可以帮我吗？ 算法应该找到可能的最高结果。在

Answer 1

这是一个很好的例子，你想用动态编程。实现这个算法有很多种方法，下面我来画一个（不是最佳的）。在

对于每个前缀长度（0到N），您可以记住该前缀所能达到的最佳分数。显然，长度为0的前缀的最佳分数是0。您可以用减号来初始化其他前缀（每个字符加1分）。在

现在，迭代这些位置，并尝试匹配该位置的所有字典单词（我们称之为K）。如果有匹配项，则将位置（K+匹配单词的长度，我们称之为L）处的最佳分数更新为max（scores[L]，scores[K]+word_score）。最终结果将是位置分数[len（string）]。在

def get_score(dct, to_score):
    dp = [-i for i in xrange(len(to_score) + 2)]
    for i in xrange(len(to_score)):
        for word in dct:
            lw = len(word)
            if lw <= len(to_score) - i:
                if word == to_score[i:i + lw]:
                    dp[i + lw] = max(dp[i+lw], dp[i] + dct[word])
        dp[i + 1] = max(dp[i + 1], dp[i] - 1)
    return dp[len(to_score)]

dct = {"fe": 1, "je": 2, "jee": 3, "ain": 3, "dai": 5, "ne": 2, "ai": 2}

for s in ("feaineai", "fejebain", "aidaidai"):
    print "%s -> %d" % (s, get_score(dct, s))

Answer 2

首先，不要调用变量dict。我要这样做：

Edit

最后阅读user@dand的答案，这是正确的，我没有什么要添加的，只是一个子进程调用max函数来处理所有结果。在

a_dict = {"fe": 1, "je": 2, "jee": 3, "ain": 3, "dai": 5, "ne": 2, "ai": 2}


def words_points(w):
  return max(sub_points(w))

def sub_points(w):
    if not w:
        yield 0
        return
    for word in a_dict:
        if w.startswith(word):
            for v in sub_points(w[len(word):]):
                yield a_dict[word] + v
    for v in sub_points(w[1:]):
        yield -1 + v



for s in ("feaineai", "fejebain", "fejeain", "aiaiai", "aiaiaije"):
  print(words_points(s))

Answer 3

将以下内容视为直接递归解决方案，表格解决方案将使用较少的时间：

a_dict = {"fe": 1, "je": 2, "jee": 3, "ain": 3, "dai": 5, "ne": 2, "ai": 2}

string = "feaineai"

def p(w):
    if not w:
        yield 0
        return
    for word in a_dict:
        if w.startswith(word):
            for v in p(w[len(word):]):
                yield a_dict[word] + v
    for v in p(w[1:]):
        yield -1 + v

print max(p(string))

为feaineai打印7，为fejebain打印{}，为aidaidai打印{}。在