本文详解如何修正递归函数，使其支持从词库中重复选取同一单词来拼凑目标字符串，并给出可运行的优化实现与关键原理说明。
本文详解如何修正递归函数，使其支持从词库中**重复选取同一单词**来拼凑目标字符串，并给出可运行的优化实现与关键原理说明。
在解决“用给定词库构造目标字符串的方案数”这类问题时，一个常见误区是将递归设计为仅遍历词库一次、每个单词最多用一次——这正是原始代码的根本缺陷。原函数 helper(index, current) 中，index 参数强制递归只能向后推进（index + 1），导致无法回退重用 word_bank[index]，因此像 "p" + "ur" + "p" + "le" 这类需重复使用 "p" 的合法组合被完全忽略。
要支持无限次复用任意单词，递归状态必须脱离“词库索引”的线性约束，转而聚焦于当前已构造的字符串前缀与剩余待匹配的目标后缀。核心思路是：对当前 current，遍历整个 word_bank，只要某个单词 w 能匹配 target 在 len(current) 位置开始的子串（即 target.startswith(w, len(current))），就将其加入并递归求解；且每次递归仍可全量遍历词库——这才是“允许重复使用”的本质。
以下是修正后的专业实现（含调试输出与清晰结构）：
def count_construct(target, word_bank):
"""
统计用 word_bank 中单词（可重复使用）拼出 target 的方案总数。
返回整数结果，不依赖全局变量，符合函数式风格。
"""
def helper(remaining):
# 基础情况：剩余为空，找到一种方案
if not remaining:
return 1
total = 0
# 尝试每个单词：若能匹配 remaining 开头，则递归处理剩余部分
for word in word_bank:
if remaining.startswith(word):
new_remaining = remaining[len(word):]
total += helper(new_remaining)
return total
return helper(target)
# 测试用例
target_example = "purple"
word_bank_example = ["purp", "p", "ur", "le", "purpl"]
print(count_construct(target_example, word_bank_example)) # 输出: 2✅ 关键改进点解析：
- 状态简化：递归参数仅保留 remaining（目标字符串的剩余未匹配部分），彻底摆脱索引限制；
- 无状态副作用：不修改外部列表或使用 nonlocal，避免隐藏的可变状态，提升可读性与可测试性；
- 精准匹配逻辑：用 remaining.startswith(word) 确保只选取真正能“接续”当前进度的单词，杜绝无效分支；
- 天然支持重复：每次递归都重新遍历完整 word_bank，"p" 可在不同层级被多次选取。
⚠️ 注意事项：
- 此算法时间复杂度为指数级（最坏 O(n^m)，n 为词库大小，m 为目标长度），对长目标或大词库需考虑记忆化优化（如 @lru_cache）；
- 若需返回所有具体组合而非仅计数，可将 helper 改为返回列表，并在匹配成功时返回 [[]]（空列表表示一种完成方案），递归合并时拼接单词；
- 输入需确保 word_bank 不含空字符串，否则将导致无限递归。
该实现不仅修复了原始逻辑缺陷，更体现了递归问题建模的核心原则：选择恰当的状态定义，让递归关系自然反映问题本质。
