Minion Game代码优化求助：解决单测试用例超时问题

问题背景 #

Kevin 和 Stuart 玩 The Minion Game，规则如下：

• 两人获得相同字符串
• 需用字符串中的字母生成子字符串
• Stuart 生成以辅音开头的子字符串，Kevin 生成以元音开头的子字符串
• 生成所有可能子字符串后游戏结束

现有代码可通过大部分测试用例，但存在一个测试用例超时，需要优化：

def minion_game(string):
    # your code goes here
    n = len(string)
    comb = ((n)*(n+1))/2
    count_k = 0
    count_s = 0
    count_k = sum([len(string[i:]) for i in range(len(string)) if string[i] in "AEIOU"])
    count_s = comb - count_k
    
    if count_s == count_k:
        print("Draw")
    elif count_s > count_k:
        print("Stuart", int(count_s) )
    else:
        print("Kevin", int(count_k))

优化方案及解释 #

原代码的主要性能瓶颈在于：

1. 列表推导式会一次性生成所有符合条件的元素列表，对于超长字符串会占用大量内存，拖慢计算速度
2. 用字符串"AEIOU"做成员判断，时间复杂度为O(5)，不如集合的O(1)高效
3. 重复调用len(string)，以及浮点数运算后再转整数，带来额外开销

优化后的代码如下：

def minion_game(string):
    vowels = {'A', 'E', 'I', 'O', 'U'}
    n = len(string)
    total_substrings = n * (n + 1) // 2
    kevin_score = sum(n - i for i, char in enumerate(string) if char in vowels)
    stuart_score = total_substrings - kevin_score
    
    if stuart_score == kevin_score:
        print("Draw")
    elif stuart_score > kevin_score:
        print("Stuart", stuart_score)
    else:
        print("Kevin", kevin_score)

关键优化点： #

• 生成器表达式替代列表推导式：sum(n - i for ...)是生成器表达式，惰性求值，不会一次性生成所有元素，大幅减少内存占用，尤其适合超长字符串
• 集合存储元音：vowels用集合存储，成员判断速度远快于字符串
• 整数运算替代浮点数：用//整数除法计算总子串数，避免后续转整数的操作
• 减少重复计算：提前存储字符串长度n，直接用n - i代替len(string[i:])，避免重复计算子串长度

这些优化能显著降低代码的时间和空间复杂度，解决超时问题。

内容的提问来源于stack exchange，提问作者Jimmy