求助：用递归实现判断字符串是否为“good”的Python函数

问题分析 #

我们需要判断一个字符串是否是"good"字符串：无论玩家A在每一步选择首字符还是尾字符，采用贪心策略（每步选当前首尾中得分最高的字符，得分相同时选最优选项）的玩家B最终总得分一定高于A。

核心思路 #

• 递归模拟游戏流程：A有两种选择（首/尾），我们需要确保这两种选择下，B按贪心策略最终都能获胜。
• 记忆化缓存重复子问题：用lru_cache缓存子字符串的计算结果，避免重复递归，提升效率。
• 得分计算：字符得分直接通过ord(char) - 96得到（a对应1，以此类推）。

完整代码实现 #

import functools

def is_word_good(word):
    @functools.lru_cache(maxsize=None)
    def get_score_diff(s, is_a_turn):
        """返回当前字符串s、当前轮到is_a_turn玩家行动时，最终B得分与A得分的差值"""
        if not s:
            return 0
        
        sc_head = ord(s[0]) - 96
        sc_tail = ord(s[-1]) - 96
        
        if is_a_turn:
            # A选首字符后的得分差值：后续B行动的差值减去A的本次得分
            diff_head = get_score_diff(s[1:], False) - sc_head
            # A选尾字符后的得分差值
            diff_tail = get_score_diff(s[:-1], False) - sc_tail
            return (diff_head, diff_tail)
        else:
            # B执行贪心策略
            if sc_head > sc_tail:
                return get_score_diff(s[1:], True) + sc_head
            elif sc_tail > sc_head:
                return get_score_diff(s[:-1], True) + sc_tail
            else:
                # 首尾得分相等时，选能最大化B得分优势的选项
                return max(get_score_diff(s[1:], True) + sc_head, 
                           get_score_diff(s[:-1], True) + sc_tail)
    
    # 检查A所有选择下，B的最终得分是否都大于A
    diff_head, diff_tail = get_score_diff(word, True)
    return diff_head > 0 and diff_tail > 0

代码说明 #

1. 记忆化缓存：@functools.lru_cache会缓存每个(s, is_a_turn)组合的计算结果，避免重复处理相同子问题，递归效率大幅提升。
2. 递归逻辑：
   • 当轮到A行动时，计算A选首和选尾两种情况的最终得分差值，返回这两个结果供主函数判断。
   • 当轮到B行动时，严格执行贪心策略：优先选得分更高的字符；若首尾得分相同，选择能让自己最终得分优势最大的路径（因为B要确保获胜）。
3. 主函数判断：只有当A的两种选择最终都让B的得分高于A（即两个差值都大于0），才返回True，说明该字符串是"good"字符串。

测试验证 #

>>> is_word_good("abc")
False
# 场景：A选首得1，B选尾得3，A再选中间得2；最终A得3，B得3，B未获胜
>>> is_word_good("asa")
True
# 场景：无论A选首还是尾，B都会选中间的's'得19分，最终A得2，B得19，B获胜

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