优化缩写问题的动态规划解决方案-Hackerrank

Question

所以我个人更喜欢使用自上而下的方法来编写动态编程解决方案。特别是在 python 中，因为它可以使用缓存装饰器实现相当简单的递归实现，正如我在下面解释的那样。

对于 Hackerrank 上的 缩写问题 ，我输入了以下解决方案（这实际上只是一个递归解决方案，利用了我们可以从缓存装饰器获得的隐式记忆）。

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）超时了。我的问题是，是否可以做一些事情来进一步优化它，以便它不会超时（保持代码的逻辑和方法基本相同）。我本以为缓存装饰器足以通过避免冗余计算来确保它在适当的时间运行。但是，也许我正在拨打一些不必要的额外电话。如果有人有任何想法，请告诉我。谢谢。

就大 o 表示法而言，我们知道这与使用自下而上的方法渐近相同，那么是什么导致这个超时呢？

我尝试过使用自下而上方法的解决方案，效果很好。我最初还有一个解决方案，该解决方案使用切片字符串的参数进行调用，但更改了调用以接受整数作为参数，以尝试进一步优化它。本来以为这就足够了。

Answer 1

你可以消除至少一段递归。

如果

a[i]

是大写，则它必须 与

b[j]

匹配。 你可以直接返回：

a[i] == b[j] and abbreviation_helper(i-1, j-1)

您正在拨打

abbreviation_helper(i-1, j)

，这是完全没有必要的，并且可能会给您错误的答案。

如果

a[i]

是小写，那么你就做对了。