Python实现的canConstruct函数特定输入下无返回值问题排查
问题排查思路
1. 记忆化功能完全失效
你在递归调用canConstruct时,没有传递memo参数,每次递归都会使用函数默认初始化的空字典,之前计算的缓存完全没有用上:
原代码递归写法:
if(canConstruct(s.replace(i,''),ls))
正确写法需要传递memo:if(canConstruct(s.replace(i,''), ls, memo))
没有记忆化的情况下,该问题的时间复杂度会达到指数级,你给出的测试用例计算量接近5千万次递归,运行耗时极长,表现为终端无输出。
2. 字符串替换逻辑错误
你使用str.replace(i, '')是全局替换所有匹配的子串,完全不符合该算法「仅匹配开头子串、移除后拼接剩余部分」的核心逻辑:
举个反例:如果s = 'efee',i = 'e',全局替换后会得到'f',但正确逻辑应该只移除开头的第一个e,剩余'fee',错误的替换逻辑会生成大量错误的递归分支,进一步加剧运行耗时。
正确的写法应该是先判断字符串是否以目标子串开头,再做切片处理:
if s.startswith(i): if canConstruct(s[len(i):], ls, memo): memo[s] = True return True
这部分逻辑可以直接替换你原有的s[0]==i[0]判断和全局替换逻辑,减少冗余判断。
3. 可变默认参数的隐藏坑
Python中函数的可变默认参数memo={}是在函数定义时初始化的,多次调用canConstruct函数时,memo会残留之前调用的缓存数据,导致逻辑错误。正确的写法应该将默认值设为None,在函数内部初始化字典:
def canConstruct(s, ls, memo=None): if memo is None: memo = {} # 后续原有逻辑不变
内容的提问来源于stack exchange,提问作者Samarth Ahuja
相关产品推荐
相关产品推荐

