python - 如何在给定列表中找到加起来为某个字符串的字符串组合（没有外部库）

Question

如果要形成的字符串是'abcde'并且输入列表是['abc', 'd', 'ac', 'ab', 'e', 'abcd'] 形成字符串'abcde'的不同方式将是

(1)'abc'+'d'+'e'

(2)'abcd'+'e'

因此答案是 2。

我该如何解决这个问题？

到目前为止我的进步;_;

character1 = input()
n = int(input())    # number of allowed inputs for list
list1 = [input() for i in range(n)]

标签： pythonpython-3.xstringcombinations

Answer 1

您可以使用递归生成器函数：

d, s = ['abc', 'd', 'ac', 'ab', 'e', 'abcd'], 'abcde'
def get_combos(d, c = []):
  if ''.join(c) == s:
     yield c
  else:
     for i in d:
        if s.startswith(''.join(c)+i):
           yield from get_combos(d, c+[i])

print(list(get_combos(d)))

输出：

[['abc', 'd', 'e'], ['abcd', 'e']]