优化Hackerrank缩写问题的自顶向下动态规划解决方案

问题描述 #

我习惯用自顶向下的动态规划（DP）写解决方案，尤其在Python里靠cache装饰器实现递归很方便。针对Hackerrank的缩写问题，我写了一个用lru_cache做记忆化的递归解法，代码如下：

def abbreviation(a, b):
    n, m = len(a), len(b)
    
    @lru_cache(maxsize=n*m)
    def abbreviation_helper(i,j):
        global a,b
        if i < j:
            return False
            
        if j == -1: 
            if a == -1 or all([a[x].islower() for x in range(i)]):
                return True
        if a[i].isupper() and a[i] != b[j]:
            return False
                
        if a[i].upper() == b[j]:
            return abbreviation_helper(i-1, j-1) or abbreviation_helper(i-1, j)
        else:
            return abbreviation_helper(i-1, j)
        
    ret = abbreviation_helper(n-1,m-1)
    if ret: 
        return "YES"
    return "NO"

这个解法结果正确，但在测试用例10、12、13、14中超时。我原以为lru_cache避免重复计算就能保证运行时间，但可能存在多余的调用。想请教在基本保留现有逻辑和实现方式的前提下，怎么优化解决超时？另外，从大O复杂度看，这个方案和自底向上方法渐近复杂度一样，为什么会超时？我试过自底向上的方案，运行正常；最初用切片字符串当参数，后来改成整数索引优化，但还是没解决超时。

优化方案（保留递归逻辑） #

1. 移除冗余的全局变量引用 #

代码里的global a,b完全多余——helper函数作为闭包，本来就能直接访问外层函数的a和b。全局变量查找比局部/闭包变量慢很多，去掉这行能减少不少额外开销。

2. 预处理前缀全小写检查 #

当j=-1时，原代码用all([a[x].islower() for x in range(i)])每次遍历字符，重复计算量极大。可以提前预处理一个前缀数组，把每个位置的检查结果存起来：

# is_all_lower[k] 表示a的前k个字符（0到k-1）是否全为小写
is_all_lower = [True] * (n + 1)
for k in range(1, n+1):
    is_all_lower[k] = is_all_lower[k-1] and a[k-1].islower()

之后j=-1时直接返回is_all_lower[i+1]即可，不用再实时遍历。

3. 预存字符大写结果 #

原代码每次调用a[i].upper()都会重复计算，提前把所有字符的大写版本存成列表：

a_upper = [c.upper() for c in a]

后续判断直接用a_upper[i]，节省重复调用方法的开销。

4. 优化lru_cache配置 #

不用手动指定maxsize=n*m，直接用maxsize=None（让缓存自动适配），或者Python3.9+用functools.cache（无界缓存，比lru_cache在这类场景下更高效）。

优化后的完整代码 #

from functools import lru_cache

def abbreviation(a, b):
    n, m = len(a), len(b)
    a_upper = [c.upper() for c in a]
    # 预处理前缀全小写数组
    is_all_lower = [True] * (n + 1)
    for k in range(1, n+1):
        is_all_lower[k] = is_all_lower[k-1] and a[k-1].islower()
    
    @lru_cache(maxsize=None)
    def abbreviation_helper(i, j):
        if i < j:
            return False
            
        if j == -1:
            return is_all_lower[i+1]
        
        if a[i].isupper() and a_upper[i] != b[j]:
            return False
                
        if a_upper[i] == b[j]:
            return abbreviation_helper(i-1, j-1) or abbreviation_helper(i-1, j)
        else:
            return abbreviation_helper(i-1, j)
        
    return "YES" if abbreviation_helper(n-1, m-1) else "NO"

为什么渐近复杂度相同但超时？ #

递归自顶向下和自底向上的时间复杂度都是O(n*m)，但递归有不少常数级额外开销：

• 函数调用栈开销：每次递归都要创建栈帧、保存上下文，比循环访问数组慢很多；
• 缓存额外开销：lru_cache的哈希表查找、键哈希计算都有 overhead，而自底向上直接用二维数组访问，速度更快；
• 缓存局部性差：递归调用顺序不规则，CPU缓存命中率低；自底向上是顺序遍历数组，缓存命中率高；
• 原代码的冗余操作：比如全局变量查找、重复的字符大小写判断，进一步放大了开销。

这些细节在大数据量测试用例中会累积成明显的性能差距，导致递归版本超时，而自底向上版本能通过。

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