问题：
给定任意字符串，如何在线性时间内添加最少的字符，使它成为回文字符串？
我只能想到一个O(N^2)的解决方案。
有人能帮我提供一个O(N)的解决方案吗？
给定任意字符串，如何在线性时间内添加最少的字符，使它成为回文字符串？
我只能想到一个O(N^2)的解决方案。
有人能帮我提供一个O(N)的解决方案吗？
添加最少的字符以使其成为回文字符串
8
- Waley Chen
2
难道你不只是需要将字符串的另一半中的每个字母更改为另一半中的字母吗？ - smac89
2我们只能在末尾添加字符吗？还是可以在任意位置添加？ - Bernhard Barker
11个回答
5
- 反转字符串
- 使用修改后的Knuth-Morris-Pratt算法来查找最新匹配（最简单的修改是将原始字符串附加到反转字符串上，并忽略长度为string的匹配）。
- 将未匹配的反转字符串的剩余部分追加到原始字符串上。
1和3显然是线性的，2也是线性的，因为Knuth-Morris-Pratt是线性的。
- Chronial
4
如果只允许添加
Scala的解决方案：
def isPalindrome(s: String) = s.view.reverse == s.view
def makePalindrome(s: String) =
s + s.take((0 to s.length).find(i => isPalindrome(s.substring(i))).get).reverse
如果您可以在任何地方插入字符
每个回文都可以看作是一组嵌套的字母对。
a n n a b o b
| | | | | * |
| -- | | |
--------- -----
如果回文字符串长度为偶数，我们将有n/2对。如果长度为奇数，我们将有n/2对以及中间的一个单独字符（让我们称其为退化对）。
我们可以用字符串索引对来表示这些对 - 左索引从字符串左端开始计数，右索引从字符串右端开始计数，两个端点都从索引0开始。
现在，让我们从外到内编写这些对。所以在我们的例子中：
anna: (0, 0) (1, 1)
bob: (0, 0) (1, 1)
为了使任何字符串成为回文，我们将从字符串的两端一次一个字符地进行，每一步，我们最终会添加一个字符以产生一对正确的相同字符。
例如： 假设输入单词为"blob"
1. 对(0, 0)进行配对是(b, b) ok，不需要操作，这个配对很好。我们增加计数器。 2. 对(1, 1)进行配对是(l, o)，不匹配。所以让我们在左边的位置1上添加"o"。现在我们的单词变成了"bolob"。 3. 对(2, 2)进行配对。我们不需要查看字符，因为我们指向字符串中的相同索引。完成。
等等，但我们有一个问题：在第2点中，我们随意选择在左边添加一个字符。但我们也可以在右边添加一个字符"l"。这将产生"blolb"，也是一个有效的回文。那么它有关系吗？不幸的是，因为早期步骤的选择可能会影响我们必须修复多少对以及因此我们将不得不在未来步骤中添加多少字符，所以它确实有关系。
简单算法：搜索所有可能性。这将给我们带来O(2^n)的算法。 更好的算法：使用动态规划方法并修剪搜索空间。
为了使事情更简单，现在我们将插入新字符与仅查找正确的嵌套对序列（从外到内）和稍后修复它们的对齐分离。因此，对于单词"blob"，我们有以下可能性，都以退化的一对结束：
(0, 0) (1, 2)
(0, 0) (2, 1)
我们找到的这些配对越多，我们就需要添加的字符就越少。每找到一个完整的配对，我们就可以重复使用两个字符。每找到一个退化的配对，我们就可以重复使用一个字符。
算法的主循环将迭代地评估这样的配对序列，以便在第一步中找到所有长度为1的有效配对序列。下一步将评估长度为2的序列，第三步将评估长度为3的序列，以此类推。当某个步骤中没有可能性时，这意味着前一步包含具有最大配对数的解决方案。
在每个步骤之后，我们将删除帕累托次优序列。如果一个序列的最后一个配对被另一个序列的最后一个配对所支配，则该序列相对于同一长度的另一个序列是次优的。例如，序列（0, 0）（1, 3）比（0, 0）（1, 2）更差。后者给我们更多的空间来找到嵌套的配对，并且我们保证至少会找到前者找到的所有配对。但是，以退化配对结尾的序列始终比以完整配对结尾的序列差。
将所有内容整合在一起：
def makePalindrome(str: String): String = {
/** Finds the pareto-minimum subset of a set of points (here pair of indices).
* Could be done in linear time, without sorting, but O(n log n) is not that bad ;) */
def paretoMin(points: Iterable[(Int, Int)]): List[(Int, Int)] = {
val sorted = points.toSeq.sortBy(identity)
(List.empty[(Int, Int)] /: sorted) { (result, e) =>
if (result.isEmpty || e._2 <= result.head._2)
e :: result
else
result
}
}
/** Find all pairs directly nested within a given pair.
* For performance reasons tries to not include suboptimal pairs (pairs nested in any of the pairs also in the result)
* although it wouldn't break anything as prune takes care of this. */
def pairs(left: Int, right: Int): Iterable[(Int, Int)] = {
val builder = List.newBuilder[(Int, Int)]
var rightMax = str.length
for (i <- left until (str.length - right)) {
rightMax = math.min(str.length - left, rightMax)
val subPairs =
for (j <- right until rightMax if str(i) == str(str.length - j - 1)) yield (i, j)
subPairs.headOption match {
case Some((a, b)) => rightMax = b; builder += ((a, b))
case None =>
}
}
builder.result()
}
/** Builds sequences of size n+1 from sequence of size n */
def extend(path: List[(Int, Int)]): Iterable[List[(Int, Int)]] =
for (p <- pairs(path.head._1 + 1, path.head._2 + 1)) yield p :: path
/** Whether full or degenerated. Full-pairs save us 2 characters, degenerated save us only 1. */
def isFullPair(pair: (Int, Int)) =
pair._1 + pair._2 < str.length - 1
/** Removes pareto-suboptimal sequences */
def prune(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = {
val allowedHeads = paretoMin(sequences.map(_.head)).toSet
val containsFullPair = allowedHeads.exists(isFullPair)
sequences.filter(s => allowedHeads.contains(s.head) && (isFullPair(s.head) || !containsFullPair))
}
/** Dynamic-Programming step */
@tailrec
def search(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = {
val nextStage = prune(sequences.flatMap(extend))
nextStage match {
case List() => sequences
case x => search(nextStage)
}
}
/** Converts a sequence of nested pairs to a palindrome */
def sequenceToString(sequence: List[(Int, Int)]): String = {
val lStr = str
val rStr = str.reverse
val half =
(for (List(start, end) <- sequence.reverse.sliding(2)) yield
lStr.substring(start._1 + 1, end._1) + rStr.substring(start._2 + 1, end._2) + lStr(end._1)).mkString
if (isFullPair(sequence.head))
half + half.reverse
else
half + half.reverse.substring(1)
}
sequenceToString(search(List(List((-1, -1)))).head)
}
注意：该代码未列出所有回文，但仅提供一个示例，保证其长度最小。通常情况下，有可能存在许多与最小长度相同的回文（在最坏情况下为O（2^n），因此您可能不想枚举它们全部）。
- Piotr Kołaczkowski
1
你的第一个解决方案（仅追加）具有二次运行时间，对吗？ - Chronial
2
我认为@Chronical的答案是错误的，因为它似乎是针对最佳情况而不是用于计算大O复杂度的最坏情况。我欢迎证据，但这个“解决方案”实际上并没有描述一个有效的答案。
KMP在
要解决这个问题，我们需要在字符串末尾找到最长的回文子串。如果这个最长后缀回文串的长度为
将KMP算法分解成下面两部分：
KMP在
O(n * 2k)时间内找到匹配的子字符串，其中n是输入字符串的长度，k是我们正在搜索的子字符串，但不能在O(n)的时间内告诉你输入字符串中最长的回文子串是什么。要解决这个问题，我们需要在字符串末尾找到最长的回文子串。如果这个最长后缀回文串的长度为
x，则添加的最小字符数为n-x。例如，字符串aaba的最长后缀子串是长度为3的aba，因此我们的答案是1。判断一个字符串是否是回文字符串的算法需要O(n)时间，无论是使用KMP还是更有效且简单的算法（O(n/2)）：
使用简单的算法，我们从整个字符串开始，检查它是否是回文字符串。如果是，我们就返回使用两个指针，一个在第一个字符处，另一个在最后一个字符处
比较指针处的字符，如果它们相等，则将每个指针向内移动，否则返回
false当指针指向同一索引（奇数长度的字符串）或重叠（偶数长度的字符串）时，返回
true
0；如果不是，我们就检查字符串string[1...end]、string[2...end]，直到达到单个字符并返回n-1。这导致了O(n^2)的运行时间。将KMP算法分解成下面两部分：
构建表格需要构建表格
搜索最长后缀回文串
O(n)的时间，然后对每个子字符串string[0...end], string[1...end], ..., string[end-2...end]进行“你是回文字符串吗”的每个检查都需要O(n)的时间。在此情况下，k是与简单算法所需的检查每个子字符串相同的因素，因为它从k=n开始，然后经过k=n-1、k=n-2...就像简单算法一样。
TL;DR：
KMP算法可以在 O(n) 时间内判断一个字符串是否为回文，但这并没有解决问题，因为你需要检查所有子串 string[0...end], string[1...end], ..., string[end - 2...end] 是否是回文，导致时间复杂度与简单的回文检查算法相同（甚至更差）。
- Austin
2
O(n)时间复杂度的解法。 算法： 需要在给定的字符串中找到包含最后一个字符的最长回文子串。然后将所有不属于回文子串的字符按相反的顺序添加到字符串的末尾。
关键点： 在这个问题中，给定字符串中最长的回文子串必须包含最后一个字符。
例如： 输入：abacac 输出：abacacaba 在这里，输入中包含最后一个字母的最长回文子串是“cac”。因此，将“cac”之前的所有字母按相反的顺序添加到后面，使整个字符串成为回文。
使用C#编写，其中几个测试用例被注释掉了。
static public void makePalindrome()
{
//string word = "aababaa";
//string word = "abacbaa";
//string word = "abcbd";
//string word = "abacac";
//string word = "aBxyxBxBxyxB";
//string word = "Malayal";
string word = "abccadac";
int j = word.Length - 1;
int mark = j;
bool found = false;
for (int i = 0; i < j; i++)
{
char cI = word[i];
char cJ = word[j];
if (cI == cJ)
{
found = true;
j--;
if(mark > i)
mark = i;
}
else
{
if (found)
{
found = false;
i--;
}
j = word.Length - 1;
mark = j;
}
}
for (int i = mark-1; i >=0; i--)
word += word[i];
Console.Write(word);
}
}
请注意，此代码将为您提供添加到字符串末尾的最少字母数量以使其成为回文的解决方案。如果要在前面添加，则只需有第二个循环以相反的方式进行即可。这将使算法为O(n) + O(n) = O(n)。如果您想要一种在字符串中任何位置插入字母以使其成为回文的方法，则此代码不适用于该情况。
- user2230558
1
如果有人想用Ruby解决这个问题，解决方案可能非常简单。
str = 'xcbc' # Any string that you want.
arr1 = str.split('')
arr2 = arr1.reverse
count = 0
while(str != str.reverse)
count += 1
arr1.insert(count-1, arr2[count-1])
str = arr1.join('')
end
puts str
puts str.length - arr2.count
- Abhilash Reddy
1
#include<iostream>
#include<string>
using std::cout;
using std::endl;
using std::cin;
int main() {
std::string word, left("");
cin >> word;
size_t start, end;
for (start = 0, end = word.length()-1; start < end; end--) {
if (word[start] != word[end]) {
left.append(word.begin()+end, 1 + word.begin()+end);
continue;
}
left.append(word.begin()+start, 1 + word.begin()+start), start++;
}
cout << left << ( start == end ? std::string(word.begin()+end, 1 + word.begin()+end) : "" )
<< std::string(left.rbegin(), left.rend()) << endl;
return 0;
}
我不知道它是否生成了最小数字，但它生成回文数。
解释：
- 我们将从给定字符串的两端开始迭代并向中心移动。
在每次迭代中，我们检查每个字符是否相同，即
word[start]==word[end]？- 如果它们相同，则将变量
word[start]的副本附加到另一个称为left的字符串中，该字符串将在迭代完成时作为新回文字符串的左侧。然后我们将变量 (start)++ 和 (end)-- 向中心递增。 - 如果它们不相同，则将变量
word[end]的副本附加到同一字符串left中。
- 如果它们相同，则将变量
这就是算法的基础，直到循环完成。
当循环完成时，进行最后一次检查以确保如果我们得到了一个奇长度的回文字符串，则将中间字符附加到形成的新回文字符串的中间。
假设 std::string 类的 append 方法运行时间恒定，此代码的运行复杂度应为 O(N)。
- smac89
0
Using Recursion
#include <iostream>
using namespace std;
int length( char str[])
{ int l=0;
for( int i=0; str[i]!='\0'; i++, l++);
return l;
}
int palin(char str[],int len)
{ static int cnt;
int s=0;
int e=len-1;
while(s<e){
if(str[s]!=str[e]) {
cnt++;
return palin(str+1,len-1);}
else{
s++;
e--;
}
}
return cnt;
}
int main() {
char str[100];
cin.getline(str,100);
int len = length(str);
cout<<palin(str,len);
}
- vibhanshu kumar
0
看这个解决方案：
这比O(N^2)更好
问题被分成了许多子问题
例如：
原始字符串“tostotor”
反转字符串“rototsot”
在此例中，第二个位置是‘o’，因此可以通过从原始字符串中拆分出“t”和“ostot”来将其分成两个问题。
对于“t”：解决方案为1
对于“ostot”：解决方案为2，因为最长公共子序列（LCS）是“tot”，需要添加的字符是“os”
所以总共是2+1=3。
def shortPalin( S):
k=0
lis=len(S)
for i in range(len(S)/2):
if S[i]==S[lis-1-i]:
k=k+1
else :break
S=S[k:lis-k]
lis=len(S)
prev=0
w=len(S)
tot=0
for i in range(len(S)):
if i>=w:
break;
elif S[i]==S[lis-1-i]:
tot=tot+lcs(S[prev:i])
prev=i
w=lis-1-i
tot=tot+lcs(S[prev:i])
return tot
def lcs( S):
if (len(S)==1):
return 1
li=len(S)
X=[0 for x in xrange(len(S)+1)]
Y=[0 for l in xrange(len(S)+1)]
for i in range(len(S)-1,-1,-1):
for j in range(len(S)-1,-1,-1):
if S[i]==S[li-1-j]:
X[j]=1+Y[j+1]
else:
X[j]=max(Y[j],X[j+1])
Y=X
return li-X[0]
print shortPalin("tostotor")
- Ravi Teja N
0
我假设您无法替换或删除任何现有字符？
一个好的开始是反转其中一个字符串，并查找反转字符串和另一个字符串之间的最长公共子序列（LCS）。由于听起来这是一道作业或面试题，所以我将把其余部分留给您自己完成。
- smocking
0
时间复杂度为O(n)的解决方案
public static void main(String[] args) {
String givenStr = "abtb";
String palindromeStr = covertToPalindrome(givenStr);
System.out.println(palindromeStr);
}
private static String covertToPalindrome(String str) {
char[] strArray = str.toCharArray();
int low = 0;
int high = strArray.length - 1;
int subStrIndex = -1;
while (low < high) {
if (strArray[low] == strArray[high]) {
high--;
} else {
high = strArray.length - 1;
subStrIndex = low;
}
low++;
}
return str + (new StringBuilder(str.substring(0, subStrIndex+1))).reverse().toString();
}
- Kovalan V
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接