不规则表达式
不规则表达式
提问于 2017-06-18 03:07:44
我有字典(单词的名称:单词的要点)。
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
这是我的字符串
string = "feaineai"我想为单词的各个部分加分。他们的总和就是结果。
但有几种方法可以计算结果：
fe-ai-ne-ai = 1+2+2+2=7
fe-ain-e-ai = 1+3-1+2=5有没有对我有帮助的算法？算法应该找到最高可能的结果。
回答 3
Stack Overflow用户
发布于 2017-06-18 03:29:12
考虑以下作为直接递归解决方案，表的解决方案将使用更少的时间：
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打印5，为aidaidai打印12。
Stack Overflow用户
发布于 2017-06-18 03:14:49
首先，不要将变量命名为dict。这就是我要做的：
编辑
最后阅读用户@Dan D.的答案，这是正确的，我没有什么要添加的，只是一个子过程对所有结果调用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))Stack Overflow用户
发布于 2017-06-18 03:34:43
这是一个很好的例子，你想要使用动态编程的问题。有很多方法可以实现算法，让我在下面概述一种(不是最优的)。
对于每个前缀长度(0到N)，您可以记住该前缀可以获得的最佳分数。显然，长度为0的前缀的最佳分数是0。您可以使用减去其长度(每个字符为-1点)来初始化其他前缀。
现在，您迭代位置并尝试匹配该位置处的所有字典单词(我们称其为K)。如果存在匹配，则将位置处的最佳分数(K +匹配单词的长度，我们称其为L)更新为max(scoresL，scoresk + word_score)。最终结果将位于scoreslen(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))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44608414
复制相关文章
相似问题
腾讯云开发者
