python - 递归 - 你如何从特定的遍历中提取

Question

假设你有一个字符串:abcde

还有一组字符串:ab、cde、abcd、a、bcd、cd

您想从构成字符串的集合中找到所有可能的串联。

您可以使用递归遍历集合中所有可能的串联，但您如何只返回满足解决方案的那些呢？

可能的组合:

ab - cde - yes
ab - cd - no
abcd - no
a - bcd - no
ab - cd - no

您可以从遍历构建一棵树，然后提取完成的路径。有没有不用树的方法？

我正在用 Python 实现这个，但请随意用任何语言回答。

Answer 1

一种可能性是将搜索构造为生成器。在 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')]

随着搜索的进行，您还可以将所有结果累积到一个列表中。