我正在解决一个问题，必须确定一个字符串是否是其他字符串的串联（这些字符串可以在串联的字符串中重复）。我正在使用回溯尽可能高效。如果字符串是串联，它将打印它是串联的字符串。如果没有，它将打印NOT POSSIBLE. 这是我的python代码：
# note: strList has to have been sorted
def findFirstSubstr(strList, substr, start = 0):
index = start
if (index >= len(strList)):
return -1
while (strList[index][:len(substr)] != substr):
index += 1
if (index >= len(strList)):
return -1
return index
def findPossibilities(stringConcat, stringList):
stringList.sort()
i = 0
index = 0
substr = ''
resultDeque = []
indexStack = []
while (i < len(stringConcat)):
substr += stringConcat[i]
index = findFirstSubstr(stringList, substr, index)
if (index < 0):
if (len(resultDeque) == 0):
return 'NOT POSSIBLE'
else:
i -= len(resultDeque.pop())
index = indexStack.pop() + 1
substr = ''
continue
elif (stringList[index] == substr):
resultDeque.append(stringList[index])
indexStack.append(index)
index = 0
substr = ''
i += 1
return ' '.join(resultDeque)
我一直在测试用例的后半部分失败，但不知道为什么。对于任何会失败的情况，有人可以提示我朝着正确的方向前进吗？谢谢！
首先，这段代码是不必要的复杂。例如，这是一个等效但更短的解决方案：
def findPossibilities(stringConcat, stringList):
if not stringConcat: # if you want exact match, add `and not stringList`
return True
return any(findPossibilities(stringConcat[len(s):],
stringList[:i] + stringList[i+1:]) # assuming non-repeatable match. Otherwise, simply replace with `stringList`
for i, s in enumerate(stringList)
if stringConcat.startswith(s))
实际回答：
边界条件：剩余部分stringConcat匹配一些stringList，停止搜索：
>>> findPossibilities('aaaccbbbccc', ['aaa', 'bb', 'ccb', 'cccc'])
'aaa ccb bb'
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句