string - Hackerrank `super-functional-strings` 因超时而终止

Question

给定一个由小写字母组成的字符串，p，计算函数的总和 F(p) = [len(p)**distinct(p)]%[10**9 + 7] 遍历 F 的所有可能的不同子串。由于结果很大，因此打印它对 10**9 + 7 取模。

例如，对于“aba”，它是:

• F(a) = 1
• F(ab) = 4
• F(aba) = 9
• F(b) = 1
• F(ba) = 4

总和等于 19。

以下是我的解决方案:

import os
import sys

def superFunctionalStrings(s):
    a=list()
    thesum=0
    length = len(s) + 1
    modu=10**9 + 7
    for j in range(length):
        for i in range(j+1, length):
            b = s[j:i]
            if b not in a:
                a.append(b)
                thesum += (len(b)**len(set(b)))%(modu)
    summ = thesum%(modu)       
    return(summ)         

我可以做些什么来优化它，以免发生超时？ (我猜外部库是不允许的)

Answer 1

你说“不同的子字符串”，所以对于初学者来说，使用一个集合而不是一个列表，这样就不会存储重复的子字符串，这样你就可以获得 O(1) 的查找时间。另外，直到最后才需要模数，并且 Python 支持任意大整数的加法，因此循环内不一定需要模数。最后，我会尝试使用推导式，以便 Python 可以更快地循环。以下是这些建议给您带来的结果:

def superFunctionalStrings(s):
    a=list()
    thesum=0
    length = len(s) + 1
    modu=10**9 + 7
    substrs = {s[j:i] for j in range(length) for i in range(j+1, length)}
    return sum(len(b) ** len(set(b)) for b in substrs) % modu

通过采用这种方法，我的速度提高了约 15-20 倍。