在做 LeetCode 139. 单词拆分时，通过记忆化函数法解题总是超时。经过了解，问题主要出在递归调用耗时太多，在 Python 语言下需要使用函数装饰器 @functools.lru_cache ，该装饰器为函数提供缓存功能，当某一函数的两次调用参数均一致，则直接返回前一次调用的结果。以下是修改后的 AC 答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        # 使用函数装饰器
        import functools 
        # @functools.lru_cache(None)
        @functools.cache
        def recall(string: str, ptr_start: int, ptr_end: int) -> bool:
            if ptr_start == len(string):
                return True
            while ptr_end <= len(string):
                if string[ptr_start:ptr_end] in wordDict and recall(string, ptr_end, ptr_end + 1):
                    return True 
                ptr_end += 1
            return False
                
        return recall(s, 0, 1)

使用注意事项

官方文档是这么形容这个函数装饰器的：

@functools.lru_cache(user_function)

@functools.lru_cache(maxsize=128, typed=False)

一个为函数提供缓存功能的装饰器，缓存 maxsize 组传入参数，在下次以相同参数调用时直接返回上一次的结果。用以节约高开销或I/O函数的调用时间。

由于使用了字典存储缓存，所以被装饰函数的固定参数和关键字参数必须是可哈希的。例如 list、dict 等数据结构都无法被 hash，因此被装饰函数不能拥有这些类型的参数。

1
2
# 这个函数无法使用 lru_cache 装饰器，因为有不可 hash 的字典类参数 map
def recall(string: str, ptr_start: int, ptr_end: int, map: dict) -> bool:

对于缓存容量，文档有如下表述

LRU（最久未使用算法）缓存在最近的调用是即将到来的调用的最佳预测值时性能最好（例如，新闻服务器上最热门文章倾向于每天更改）。 缓存的大小限制可确保缓存不会在长期运行进程如网站服务器上无限制地增长。

如果 maxsize 设为 None，LRU 特性将被禁用且缓存可无限增长。

这意味着，在需要 LRU 功能的业务逻辑中使用该装饰器时应当注意设置缓存大小，一般设为2的多次幂性能较高。但在刷题，设计算法时，直接传入 None 参数更好，因为大部分算法题不需要使用到 LRU 特性，且无限的缓存容量能保证高效处理大数据量的用例。并且官方文档指出，不考虑使用 LRU 功能的前提下，使用 None 参数的装饰器性能更好：

因为它不需要移出旧值，所以比带有大小限制的 lru_cache() 更小更快。

如果采用 3.9 版本以上的 Python 编译器，则建议使用 @functools.cache ，它与 @functools.lru_cache(None) 是等价的。