You need to enable JavaScript to run this app. Python实现的canConstruct函数特定输入下无返回值问题排查
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.20 21:24:03