python - 算法问题，python字符串，不知道

Question

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

我的问题:

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

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

我尝试使用 string.count 函数和计数子串，但这种方法并不好。 在 Python 中执行此操作的最佳方法是什么？提前致谢。

string = "aeafirefi"

对子串的值求和。

Answer 1

在我的解决方案中，我将使用 itertools 模块中的 permutations 来列出您在问题中给出的子字符串的所有可能排列，并将其呈现给名为 vals。然后遍历输入字符串并按下面找到的所有排列拆分字符串。然后对每个排列的值求和，最后得到最大值。

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))

输出:

Sublists: ('ae', 'afi', 're', 'fi')
Sum: 16
----
Sublists: ('afi', 'ae', 'qdd', 're', 'fi')
Sum: 21
----
Sublists: ('afi', 'ae', 'qdd', 're', 'fi')
Sum: 1

请尽可能使用许多输入字符串尝试此解决方案，如果发现任何错误结果，请不要犹豫，发表评论。