如何用DFS实现从单词列表中找出匹配目标单词的分词组合？

你要解决的是找出所有能拼接成目标单词sometime的有效单词组合，有效单词列表是["some","time","rome","sometime","so","me"]，预期输出为[["so","me","time"],["some","time"],["sometime"]]。你当前的DFS代码存在多处逻辑问题，下面是修正后的实现和问题分析：

原代码的问题点 #

• 参数逻辑混乱：string_path是剩余待处理字符串，但你同时用i去截取string_path[:i]，导致剩余字符串和索引的逻辑完全冲突，比如递归传word[i:]时，i还是原单词的索引，和剩余字符串长度不匹配。
• 终止条件缺失：只判断i == len(word)就返回，没处理剩余字符串为空的情况，无法将有效组合存入结果。
• 起始循环无效：外层循环从0开始，word[:0]是空字符串，不在有效单词列表中，这部分循环完全没用。
• 无回溯操作：递归时直接修改curr_string但没在返回后移除当前单词，会导致后续组合被错误污染。
• 查找效率低：直接用列表做存在性检查，时间复杂度高，应该转成集合。

修正后的DFS实现 #

def word_break_combinations(target_word, valid_words):
    result = []
    valid_word_set = set(valid_words)  # 转集合加速查找，O(1)时间复杂度

    def dfs(remaining, current_combination):
        # 终止条件：剩余字符串为空，说明找到一个有效组合
        if not remaining:
            result.append(current_combination.copy())
            return
        
        # 遍历所有可能的前缀长度，从1到剩余字符串的长度
        for i in range(1, len(remaining) + 1):
            prefix = remaining[:i]
            if prefix in valid_word_set:
                # 选择当前单词，加入组合
                current_combination.append(prefix)
                # 递归处理剩余的字符串部分
                dfs(remaining[i:], current_combination)
                # 回溯：移除当前单词，尝试其他可能的前缀
                current_combination.pop()

    # 启动DFS，初始剩余字符串是目标单词，组合为空
    dfs(target_word, [])
    return result

# 测试用例
target = "sometime"
valid = ["some","time","rome","sometime","so","me"]
print(word_break_combinations(target, valid))
# 输出：[['sometime'], ['some', 'time'], ['so', 'me', 'time']]

代码逻辑说明 #

1. 集合优化：将有效单词列表转为集合，大幅提升存在性检查的效率。
2. DFS核心逻辑：
   • remaining：当前尚未处理的剩余字符串，每次递归只关注这部分。
   • current_combination：当前已经选中的单词组合，用于记录路径。
3. 终止条件：当剩余字符串为空时，说明当前组合刚好拼接成目标单词，将组合的副本加入结果（必须用copy()，否则后续回溯修改会影响已存入的结果）。
4. 遍历与回溯：尝试剩余字符串的所有可能前缀，若前缀是有效单词，则加入组合并递归处理剩余部分；递归返回后，移除当前单词，继续尝试其他前缀，确保所有可能的组合都被遍历到。

内容的提问来源于stack exchange，提问作者Alice the SWE