我有一个问题,我需要一个算法来解决它.
我找不到它,我不知道问题是否是NP-Hard.
问题是:我有几个符号序列.我想将它们合并为单个序列,其中包括原始序列的所有符号,保持符号的原始顺序.应删除来自不同序列的重复符号.结果序列必须是可能的最小序列.
如果序列之一是"abc",则得到的序列必须是*a*b*c*,其中*是0或更多符号的序列.如果输入序列是'abc'和'cba',则输出必须是'abcba','c'包含一次,并保留*a*b*c*和*c*b*a*属性.
示例:
输入:
abcde
xbcaf
axdaf
如何合并的方式:
a-bcde--
-xbc--af
ax--d-af
输出:
axbcdeaf
多个输出是可能的,'abcd'和'cba'将导致'abcdba','abcbda'或'abcbad'.我只需要一个输出,任何输出都是有效的,如果它的长度是可能的最小长度.
谢谢