这是一个理论问题,我不需要它用于实际目的。但我想知道是否有一些好的算法可以解决这个问题。
编辑:阅读了一些答案后,我注意到这可能是一个 NP-完全问题。即使找到一个子集字符串,它们的长度总和与给定字符串相同,也是一个经典的子集求和问题。
因此,我想这并没有容易的答案。
编辑:
现在看起来,这实际上不是 NP 完全问题。太酷了 :-)
编辑:
我已经想出了一个通过了一些测试的解决方案:
def can_build_from_substrings(string, substrings):
prefixes = [True] + [False] * (len(string) - 1)
while True:
old = list(prefixes)
for s in substrings:
for index, is_set in enumerate(prefixes):
if is_set and string[index:].startswith(s):
if string[index:] == s:
return True
prefixes[index + len(s)] = True
if old == prefixes: # nothing has changed in this iteration
return False
我认为时间复杂度是O(n * m^3)
,其中n
是子字符串
的长度,m
是字符串
的长度。你怎么看?