使用最少的插入次数将字符串转换为回文结构

Question

这是来自https://www.dailycodingproblem.com/的问题：

给定一个字符串，找到可以通过在单词中的任何位置插入尽可能少的字符来制作的回文。如果可以制作多个最小长度的回文，则返回按字典顺序排列的字典（按字母顺序排列的第一个）。

例如，给定字符串“race”，您应该返回“ecarace”，因为我们可以添加三个字母（这是制作回文的最小量）。通过添加三个字母，可以通过“种族”制作其他七个回文，但“ecarace”首先按字母顺序排列。

另一个例子，给定字符串“google”，您应该返回“elgoogle”。

它类似于this SO问题，或者this GeeksforGeeks的帖子。相似，但不一样;他们都没有对复发提供任何解释，就好像他们从空气中掏出解决方案一样，并且他们不会重建解决方案，更不用说按字典顺序最早的解决方案。

经过一番思考，我的理解如下：

观察任何字符串s[i..j]，如果s[i] == s[j]，那么使它成为回文所需的插入次数与使s[i+1..j-1]成为回文所需的插入次数相同。

然而，如果s[i] != s[j]，那么我们可以将s[i..j-1]转换为回文，然后在开头插入s[j]，或者将s[i+1..j]转换为回文并在末尾插入s[i]。由于我们正在寻找最少数量的插入，我们将选择两个选项中的最小值。插入的数量比所选子问题所需的插入数量多一个（用于在开头或结尾添加字符）。

如何重建按字典顺序排列的最早解决方案？

Answer 1

首先，让我们回答“我如何重建解决方案”，然后专注于订购。假设您将插入的数量存储在二维矩阵insertions[start][stop]中，您只需要回溯您的步骤，“收集”随时插入的字符。我们需要一个新的数组来存储输出字符串，其长度等于我们的起始字符串加上最小的插入次数。我们还将存储两个索引，指向前面和后面的数组中的下一个可用点。

首先比较当前子字符串的第一个和最后一个字母，如果相等，则分别在前面和后面的下一个可用位置分配两个输出字符串。例如，如果我们将FYRF作为当前子字符串，我们将分配输出字符串F..F，其中.是未确定的字符。我们的子串然后变成s[i+1..j-1]或YR。

如果两个字符不匹配，我们将比较我们在insertions[i+1][j]和insertions[i][j-1]中的记录，看看哪个更小（至少其中一个将比insertions[i][j]少一个）。如果他们是平等的，那就选择一个（我们稍后再回来）。在输出字符串中分配字符，该字符对应于我们复制/插入的子字符串的字母，在输出字符串中的下一个可用的前向和后向索引处。也就是说，在JLL的情况下，如果我们决定为J添加JLLJ，我们将采用子字符串s[i+1..j]，因此我们将J和J存储在输出字符串J..J中。如果我们的输出字符串已经包含AR....RA，我们已经存储了ARJ..JRA。我们重复整个过程，直到分配完所有字符。

现在，按字典顺序排序。关于前一段中insertions[i+1][j]和insertions[i][j-1]相等的情况，我们不应随意挑选其中一个。相反，我们应该按字典顺序比较s[i]和s[i+1]，如果s[i]首先出现，将s[i]插入输出字符串/继续insertions[i+1][j]。否则，请使用s[i+1] / insertions[i][j-1]。这将为我们提供所有可用选项中按字典顺序排列的最快字符串。

Answer 2

OP在这里：@ dillon-davis的回答是正确的（upvoted），虽然我当时已经弄明白了。我已经在问题中提供了基本算法的解释，@ dillon-davis提供了重构的解释，这里是Scala中完整性的工作代码。

def makePalindromeByFewestEdits(word: String): String = {
    val n = word.length
    val dp = Array.ofDim[Int](n, n)

    for (window <- 1 until n)
      (0 until n)
        .map(start => (start, start + window))
        .takeWhile(_._2 < n)
        .foreach {
          case (start, end) if word(start) == word(end) =>
            dp(start)(end) = dp(start + 1)(end - 1)
          case (start, end) =>
            dp(start)(end) = math.min(dp(start + 1)(end), dp(start)(end - 1)) + 1
        }

    val minInsertions = dp(0)(n - 1)
    val palindrome = Array.ofDim[Char](n + minInsertions)

    @tailrec
    def reconstruct(start: Int, end: Int, count: Int, offset: Int): String = {
      if (count == 0) {
        // we have written 'start' characters from the beginning, the current insertion index is 'offset', and
        // the number of characters left to be written are the substring word[start..end]
        Array.copy(word.toCharArray, start, palindrome, offset, end - start + 1)
        palindrome.mkString
      } else {
        val (s, e, c, ch) = if (word(start) == word(end))
          (start + 1, end - 1, count, word(start))
        else if (dp(start + 1)(end) < dp(start)(end - 1) ||
          (dp(start + 1)(end) == dp(start)(end - 1) && word(start) < word(end))
        )
          (start + 1, end, count - 1, word(start))
        else
          (start, end - 1, count - 1, word(end))

        palindrome(offset) = ch
        palindrome(palindrome.length - 1 - offset) = ch
        reconstruct(s, e, c, offset + 1)
      }
    }

    reconstruct(0, n - 1, minInsertions, 0)
}