比如str="abcd",则"a"、"ab"、"abc"和"abcd"都是"abcd"的前缀,"d"、"cd"、"bcd"和"abcd"都是"abcd"的后缀。
如果字符串str2的一个前缀刚好是str1的后缀,那么允许这两个字符串拼接,比如Xabc后面可以拼接上abcYZ
得到X[abc]YZ(中括号表示两个串重叠的部分)。现在给定一系列固定长度的字符串,求它们能拼接成的最短字符串。
举个例子,给定两个字符串ATCC和CCTA,它们可以拼接成ATC[C]CTA, AT[CC]TA, CCT[A]TCC,其中最短的字符串长度是6。
复杂度的说明: O(n^2*(2^n+L))可以通过所有数据。 其他的复杂度如果优化得当,也可以得分
时限维持1s
时限维持1s