如何确定字符串是否是字符串列表的串联

Question

假设我们给出了一个字符串S,以及一些其他字符串L的列表.

我们怎么知道S是否是L的所有可能连接中的一个？

例如:

S ="abcdabce"

L = ["abcd","a","bc","e"]

S是"abcd"+"a"+"bc"+"e",则S是L的串联,而"ababcecd"则不是.

为了解决这个问题,我尝试使用DFS /回溯.伪代码如下:

boolean isConcatenation(S, L) {
    if (L.length == 1 && S == L[0]) return true;
    for (String s: L) {
        if (S.startwith(s)) {
            markAsVisited(s);
            if (isConcatnation(S.exclude(s), L.exclude(s))) 
                return true;
            markAsUnvisited(s);
        }
    }
    return false;
}

但是,DFS /回溯不是一种有效的解决方案.我很好奇什么是解决这个问题的最快算法,或者是否有任何其他算法以更快的方式解决它.我希望有像KMP这样的算法可以在O(n)时间内解决它.

Answer 1

在Python中：

>>> yes = 'abcdabce'
>>> no = 'ababcecd'
>>> L = ['abcd','a','bc','e']
>>> yes in [''.join(p) for p in itertools.permutations(L)]
True
>>> no in [''.join(p) for p in itertools.permutations(L)]
False

编辑：正如所指出的，这是n！复杂，所以不适合大L。但是嘿，开发时间不到10秒。

您可以从基本排列器开始构建自己的排列生成器：

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

然后通过跟踪元素的串联方式来丢弃您不关心的分支，并且仅在它加起来达到目标​​字符串时才进行迭代。

    def all_perms(elements, conc=''):
    ...
            for perm in all_perms(elements[1:], conc + elements[0]):
    ...
                if target.startswith(''.join(conc)):
    ...