假设你有一个字符串：abcde
以及一组字符串：ab、cde、a bcd、a、bcd、cd
希望从构成字符串的集合中找到所有可能的连接。
可以使用递归遍历集合中所有可能的连接，但如何只返回满足解决方案的连接？
可能的组合：
ab - cde - yes
ab - cd - no
abcd - no
a - bcd - no
ab - cd - no
可以从遍历中构建树，然后提取完成的路径有没有不用树的方法？
我正在用python实现它，但是可以用任何语言回答。
最佳答案
一种可能性是将搜索构造为生成器。在python中，可能如下所示：
def concatenations(target_string, fragments, concat_path=()):
if not target_string:
yield concat_path
else:
for frag in fragments:
if target_string.startswith(frag):
new_target = target_string[len(frag):]
new_path = concat_path + (frag,)
for c in concatenations(new_target, fragments, new_path):
yield c
注意，我假设集合中的元素可以在字符串中出现多次如果这不合适，请在递归调用中将
fragments替换为fragments - {frag}。只需将生成器中的所有结果收集到列表中，就可以获取所有元素：
fragments = {"ab", "cde", "abcd", "a", "bcd", "cd", "e"}
list(concatenations("abcde", fragments))
这会产生：
[('a', 'bcd', 'e'), ('abcd', 'e'), ('ab', 'cde'), ('ab', 'cd', 'e')]
在搜索过程中，您还可以将所有结果累积到一个列表中。