string - 找到通过合并两个字符串形成的最小词法字符串

Question

假设我们有两个字符串 s1 和 s2(均为小写)。我们有两个找到可以通过合并两个字符串形成的最小 lexographic 字符串。

一开始，它看起来很简单，就像归并排序算法的归并。但是让我们看看会出现什么问题。

s1: zyy

s2: z

现在如果我们对这两个执行合并，我们必须决定选择哪个 z，因为它们是相等的，显然如果我们首先选择 s2 的 z，那么形成的字符串将是:

很开心

如果我们先从 s1 中选择 z，则形成的字符串将是:

zyyzy 这是正确的。

正如我们所见，mergesort 的合并会导致错误的答案。

这是另一个例子:

s1:zyy

s2:zb

现在正确答案将是 zybzyy，只有先选择 s2 的 z 才能得到。

还有很多其他情况下简单合并会失败。我的问题是是否有任何标准算法用于对此类输出执行合并。

Answer 1

您可以使用动态规划。在 f[x][y]存储最小的字典字符串，这样你就可以使用 x来自第一个字符串的字符 s1和 y第二个字符 s2 .你可以计算出f以自下而上的方式使用更新:

f[x][y] = min(f[x-1][y] + s1[x], f[x][y-1] + s2[y]) \\ the '+' here represents
                                                    \\ the concatenation of a 
                                                    \\ string and a character

您从 f[0][0] = "" (empty string) 开始.

为了提高效率，您可以将字符串存储在 f 中作为引用。也就是说，你可以存储在f对象

class StringRef {
    StringRef prev;
    char c;
}

要提取您在某个 f[x][y] 处的字符串你只要按照引用。要更新，请指向 f[x-1][y]或 f[x][y-1]取决于您的更新步骤。