算法问题，python字符串，无id

Question

我有关于Python和字符串的算法问题。在

我的问题：

我的函数应该求和子字符串的最大值。 例如：

ae-afi-re-fi -> 2+6+3+5=16
but 
ae-a-fi-re-fi -> 2-10+5+3+5=5

我试着用字符串.count函数和计数子串，但这种方法不好。 在Python中最好的方法是什么？提前谢谢。在

^{pr2}$

将子字符串的值求和。在

Answer 1

可能有一本字典： 键=子字符串：值=值

所以如果你有：
string=“aeafirefi”

首先你要在字典里寻找整个字符串，如果你找不到，你就把最后一个字母剪成“aeafiref”，直到你找到一个子串或者只有一个字母。在

然后跳过使用的字母：例如，如果找到“aeaf”，则使用string=“iref”重新开始。在

Answer 2

在我的解决方案中，我将使用来自itertools模块的permutations来列出你在你的问题中给出的所有可能的子串的排列，这些子串将呈现在一个名为vals的dict中。然后迭代输入字符串并按下面找到的所有排列拆分字符串。然后将每个排列的值相加，最后得到最大值

PS:这个解决方案的关键是get_sublists()方法。在

以下是一些测试的示例：

from itertools import permutations 

def get_sublists(a, perm_vals):
    # Find the sublists in the input string
    # Based on the permutations of the dict vals.keys()
    for k in perm_vals:
        if k in a:
            a = ''.join(a.split(k))
            # Yield the sublist if we found any
            yield k

def sum_sublists(a, sub, vals):
    # Join the sublist and compare it to the input string
    # Get the difference by lenght
    diff = len(a) - len(''.join(sub))
    # Sum the value of each sublist (on every permutation)
    return sub , sum(vals[k] for k in sub) - diff * 10

def get_max_sum_sublists(a, vals):
    # Get all the possible permutations
    perm_vals = permutations(vals.keys())
    # Remove duplicates if there is any
    sub = set(tuple(get_sublists(a, k)) for k in perm_vals)
    # Get the sum of each possible permutation
    aa = (sum_sublists(a, k, vals) for k in sub)
    # return the max of the above operation
    return max(aa, key= lambda x: x[1])


vals = {'ae': 2, 'qd': 3, 'qdd': 5, 'fir': 4, 'afi': 6, 're': 3, 'fi': 5}

# Test
a = "aeafirefi"
final, s = get_max_sum_sublists(a, vals)
print("Sublists: {}\nSum: {}".format(final, s))
print('  ')
a = "aeafirefiqdd"
final, s = get_max_sum_sublists(a, vals)
print("Sublists: {}\nSum: {}".format(final, s))
print('  ')
a = "aeafirefiqddks"
final, s = get_max_sum_sublists(a, vals)
print("Sublists: {}\nSum: {}".format(final, s))

输出：

^{pr2}$

请尽可能使用多个输入字符串来尝试此解决方案，如果发现任何错误的结果，请立即发表评论。在

Answer 3

这里有一个暴力解决方案：

values_dict = {
    'ae': 2,
    'qd': 3,
    'qdd': 5,
    'fir': 4,
    'afi': 6,
    're': 3,
    'fi': 5
}

def get_value(x):
    return values_dict[x] if x in values_dict else -10

def next_tokens(s):
    """Returns possible tokens"""
    # Return any tokens in values_dict
    for x in values_dict.keys():
        if s.startswith(x):
            yield x

    # Return single character.
    yield s[0]

def permute(s, stack=[]):
    """Returns all possible variations"""

    if len(s) == 0:
        yield stack
        return

    for token in next_tokens(s):
        perms = permute(s[len(token):], stack + [token])
        for perm in perms:
            yield perm

def process_string(s):
    def process_tokens(tokens):
        return sum(map(get_value, tokens))

    return max(map(process_tokens, permute(s)))

print('Max: {}'.format(process_string('aeafirefi')))