将插入次数最少的字符串转换为回文 [英] Convert string to palindrome with fewest number of insertions

问题描述

这是来自 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).

例如，给定字符串"race"，您应该返回"ecarace"， 因为我们可以在其中添加三个字母(这是 做回文).还有其他七种回文 从种族"中添加三个字母，但"ecarace"排在第一位 按字母顺序.

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.

作为另一个示例，给定字符串"google"，您应该返回 "elgoogle".

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

它类似于此 SO问题，或

It is similar to this SO question, or this GeeksforGeeks post. Similar, but not the same; none of them provide any explanation for the recurrence, as if they plucked the solution out of thin air, and they don't reconstruct the solution, let alone the lexicographically earliest one.

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

After some thinking, my understanding is as follows:

对于任何字符串s[i..j]，请注意，如果s[i] == s[j]，则 使其回文所需的插入次数与 使s[i+1..j-1]回文所需的插入次数.

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.

但是，如果s[i] != s[j]，那么我们可以将s[i..j-1]转换为 回文，然后在开头插入s[j]或进行转换 s[i+1..j]到回文，并在最后插入s[i].既然我们是 在寻找最少插入次数的情况下，我们将选择 这两个选项中的最小值.插入次数多于 所选子问题所需的插入次数(对于 在开头或结尾添加一个字符.

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).

我如何重建词典上最早的解决方案?

How do I reconstruct the lexicographically earliest solution?

推荐答案

首先，让我们回答如何重建解决方案"，然后着眼于订购.假设您将插入次数存储在2D矩阵insertions[start][stop]中，则只需回溯您的步骤，即可收集"插入的字符.我们需要一个新的数组来存储输出字符串，其长度等于我们的起始字符串加上最少的插入次数.我们还将存储两个索引，指向从正面到阵列的下一个可用点.

First, lets answer "how do I reconstruct the solution", then focus on ordering. Assuming you store the number of insertions in a 2D matrix insertions[start][stop], you just need to retrace your steps, "collecting" the characters inserted as you go. We'll need a new array to store out output string, of length equal to our starting string plus the minimal number of insertions. We'll also store two indices, pointing to the next available spots from the front and back into the array.

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

Start by comparing the first and last letters of the current substring, and if equal assign the output string both of those, in the next available positions from the front and back respectively. For example, if we have FYRF as our current substring, we'll assign our output string F..F, where . are undetermined characters. Our substring then becomes s[i+1..j-1] or YR.

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

If the two characters do not match, we'll compare our records in insertions[i+1][j] and insertions[i][j-1], to see which is smaller (at least one of them will be exactly one less than insertions[i][j]). If they're equal, just pick one (we'll return to this later). Assign the character in our output string which corresponds to the letter of the substring we duplicated / inserted, at the next available front and back indices into the output string. That is, in the case JLL, if we decide to add a J for JLLJ, we'd take the substring s[i+1..j], so we'd store J and J in our output string J..J. If our output string already contained AR....RA, we'd have stored ARJ..JRA instead. We repeat this entire process until all characters are assigned.

现在，按照字典顺序对其进行排序.关于上一段中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].从所有可用选项中，这将为我们提供字典上最早的字符串.

Now, to make it ordered lexicographically. Regarding the case in the previous paragraph where insertions[i+1][j] and insertions[i][j-1] are equal, we shouldn't pick one of them at random. Instead, we should compare s[i] and s[i+1] lexicographically, and if s[i] comes first, insert s[i] into the output string / proceed on insertions[i+1][j]. Otherwise, use s[i+1] / insertions[i][j-1]. This will give us the lexicographically soonest string from all available options.

这篇关于将插入次数最少的字符串转换为回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！