查找字符串是否是其他字符串的串联

Question

我正在处理一个问题，其中必须确定一个字符串是否是其他字符串的串联（这些字符串可以在串联的字符串中重复）。我使用回溯是为了尽可能有效。如果字符串是串联的，它将打印它是串联的字符串。否则，它将打印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)

我在最后一半的测试中一直失败，但我不知道为什么。有没有人能给我一个正确的方向，让我在任何情况下，这将失败？谢谢！你知道吗

Answer 1

首先，这个代码是不必要的。例如，下面是一个等效但较短的解决方案：

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'