如何实现从单词库生成目标字符串的所有组合？现有代码输出异常求助

原代码的核心问题 #

1. 列表初始化错误：table = [[]] * (len(target) + 1) 创建的是多个指向同一空列表的引用，修改任意一个子列表都会同步影响所有子列表，直接导致组合结果混乱。
2. 返回值逻辑不严谨：虽然循环结束后i的值恰好等于len(target)，但依赖循环变量的最终状态返回结果可读性差，且容易因循环逻辑变动出错，应直接返回table[len(target)]。

修复后的代码 #

def all_construct(target, word_bank):
    # 初始化每个元素为独立的空列表，避免引用共享
    table = [[] for _ in range(len(target) + 1)]
    table[0] = [[]]  # 空字符串的组合方式是一个空列表

    for i in range(len(target) + 1):
        # 仅当当前位置已有有效组合时，才继续处理后续单词
        if table[i]:
            for word in word_bank:
                word_len = len(word)
                # 检查当前位置开始的子串是否匹配单词
                if i + word_len <= len(target) and target[i:i+word_len] == word:
                    # 生成新组合：给当前所有组合末尾追加当前单词
                    new_combinations = [sub_list + [word] for sub_list in table[i]]
                    # 将新组合添加到对应位置
                    table[i + word_len].extend(new_combinations)

    return table[len(target)]

print(all_construct("abcdef", ["ab", "abc", "cd", "def", "abcd", "ef", "c"]))

运行结果：

[['ab', 'cd', 'ef'], ['ab', 'c', 'def'], ['abc', 'def'], ['abcd', 'ef']]

更优思路与优化方向 #

1. 剪枝优化 #

提前跳过长度超过剩余目标字符串的单词，减少不必要的切片和比较操作：

for word in word_bank:
    word_len = len(word)
    if i + word_len > len(target):
        continue
    if target[i:i+word_len] == word:
        # 后续逻辑不变

2. 记忆化递归（备选方案） #

对于较长的目标字符串或较大的单词库，记忆化递归可避免重复计算子问题，逻辑更直观：

def all_construct(target, word_bank, memo=None):
    if memo is None:
        memo = {}
    if target in memo:
        return memo[target]
    if target == "":
        return [[]]
    
    result = []
    for word in word_bank:
        if target.startswith(word):
            suffix = target[len(word):]
            suffix_combinations = all_construct(suffix, word_bank, memo)
            target_combinations = [comb + [word] for comb in suffix_combinations]
            result.extend(target_combinations)
    
    memo[target] = result
    return result

3. 预过滤无效单词 #

预先过滤掉长度超过目标字符串、或不在目标字符串中出现的单词，减少循环次数：

filtered_word_bank = [word for word in word_bank if len(word) <= len(target) and word in target]

内容的提问来源于stack exchange，提问作者Ogbonna Stanley