如果我们有两个字母序列X和Y,我们想要找到最短的序列,使得X和Y成为该序列的子序列。这项工作的时间复杂度是多少?1)O(nm)2)O(n+m)3)O((n+m)log(n+m))我的解决方案:我找到了一种动态规划的方法,并使用了O(nm)的顺序。有更好的解决方案吗?谢谢任何人
您可以将此问题简化为查找最长公共子序列(LCS)。给定两个序列及其最长公共子序列,您可以使用类似于合并的贪心算法在线性时间内构造最短超序列,该算法从X或Y中添加字母到结果中,如果它们不在公共子序列中且前进到下一个字母。很容易证明该算法产生了最短超序列,否则它就与我们使用最长公共子序列的断言相矛盾。由于没有LCS解决方案是线性的,因此解决LCS将支配寻找此问题答案的算法。 LCS解决方案的复杂度取决于多个因素,例如字母表的长度。 通用LCS的解决方案为O(n*m)。固定字母表上的LCS解决方案为O((n+m+c)*long(n+m)),其中c是公共子序列的长度。
abcde
和bd
的预期输出是abcde
,对吗? - IVlad