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

Question

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

Given a string, find the palindrome that can be made by inserting the fewest number of characters as possible anywhere in the word. If there is more than one palindrome of minimum length that can be made, return the lexicographically earliest one (the first one alphabetically).

For example, given the string "race", you should return "ecarace", since we can add three letters to it (which is the smallest amount to make a palindrome). There are seven other palindromes that can be made from "race" by adding three letters, but "ecarace" comes first alphabetically.

As another example, given the string "google", you should return "elgoogle".

它类似于 this SO question, or this GeeksforGeeks post。相似，但不相同； none 他们中的任何人都对重现提供了任何解释，就好像他们凭空摘取解决方案一样，他们不重建解决方案，更不用说字典编年史最早的解决方案了。

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

Observe that for any string s[i..j], if s[i] == s[j], then the number of insertions required to make it a palindrome is the same as the number of insertions required to make s[i+1..j-1] a palindrome.

If, however, s[i] != s[j], then we may convert s[i..j-1] to a palindrome and then insert s[j] at the beginning, or convert s[i+1..j] to a palindrome and insert s[i] at the end. Since we are looking for the fewest number of insertions, we will choose the minimum of the two options. The number of insertions is one more than the number of insertions required for the chosen subproblem (for adding a character at the beginning or at the end).

如何重建字典序最早的解决方案？

Answer 1

首先，让我们回答 "how do I reconstruct the solution"，然后专注于订购。假设您将插入的数量存储在二维矩阵 insertions[start][stop] 中，您只需要追溯您的步骤，"collecting" 插入的字符。我们需要一个新数组来存储输出字符串，其长度等于我们的起始字符串加上最小插入次数。我们还将存储两个索引，指向数组中前后的下一个可用点。

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

如果两个字符不匹配，我们将比较 insertions[i+1][j] 和 insertions[i][j-1] 中的记录，看哪个更小（至少有一个比 insertions[i][j]).如果它们相等，就选择一个（稍后我们会 return ）。将输出字符串中对应于我们复制/插入的子字符串的字母的字符分配到输出字符串的下一个可用前后索引处。也就是说，在 JLL 的情况下，如果我们决定为 JLLJ 添加 J，我们将采用子字符串 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 的回答是正确的（已投票），尽管那时我已经自己弄明白了。我已经在问题中提供了基本算法的解释，@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)
}

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

Convert string to palindrome with fewest number of insertions

string

algorithm

dynamic-programming

palindrome