问题：
给定任何字符串，添加尽可能少的字符，使其在线性时间内成为回文。
我只能想出一个 O(N 2 ) 解决方案。
有人可以帮我解决 O(N) 问题吗？
问问题
15694 次
11 回答
5
- 恢复字符串
- 使用修改后的Knuth-Morris-Pratt查找最新匹配项（最简单的修改是将原始字符串附加到恢复的字符串并忽略 len(string) 之后的匹配项。
- 将恢复的字符串的不匹配的其余部分附加到原始字符串。
1 和 3 显然是线性的，而 2 是线性的，因为 Knuth-Morris-Pratt 是。
于 2013-09-11T06:49:58.017 回答
4
如果只允许追加
斯卡拉解决方案：
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 是偶数，我们将有 n/2 对。如果它是奇数，我们将有 n/2 个完整的对，中间有一个字母（我们称之为退化对）。
让我们用成对的字符串索引来表示它们——左索引从字符串的左端开始计数，右索引从字符串的右端开始计数，两端都从索引 0 开始。
现在让我们从外到内写对。所以在我们的例子中：
anna: (0, 0) (1, 1)
bob: (0, 0) (1, 1)
为了使任何字符串成为回文，我们将一次从字符串的两端开始一个字符，并且每一步，我们最终都会添加一个字符以产生一对正确的相同字符。
示例：假设输入单词是“blob”
- 对 (0, 0) 是 (b, b) ok，没事，这对没问题。让我们增加计数器。
- 对 (1, 1) 是 (l, o)。不匹配。因此，让我们在左侧的第 1 个位置添加“o”。现在我们的词变成了“bolob”。
- 对 (2, 2)。我们甚至不需要查看字符，因为我们指向字符串中的相同索引。完毕。
稍等片刻，但我们这里有一个问题：在第 2 点中，我们任意选择在左侧添加一个字符。但是我们也可以在右边添加一个字符“l”。这将产生“blolb”，也是一个有效的回文。那么这有关系吗？不幸的是，它确实如此，因为前面步骤中的选择可能会影响我们必须修复多少对，因此我们必须在以后的步骤中添加多少字符。
简单算法：搜索所有可能性。这会给我们一个 O(2^n) 算法。更好的算法：使用动态规划方法并修剪搜索空间。
为了使事情更简单，现在我们将插入新字符与仅找到正确的嵌套对序列（从外到内）和稍后修复它们的对齐方式分离。所以对于“blob”这个词，我们有以下可能性，都以退化对结尾：
(0, 0) (1, 2)
(0, 0) (2, 1)
我们找到的这样的对越多，我们必须添加的字符就越少来修复原始字符串。找到的每一对都为我们提供了两个可以重复使用的字符。每一个退化的对都给了我们一个可以重用的字符。
该算法的主循环将以这样一种方式迭代地评估对序列，即在步骤 1 中找到所有长度为 1 的有效对序列。下一步将评估长度为 2 的序列、长度为 3 的第三个序列等。当在某个步骤我们发现没有可能性时，这意味着上一步包含具有最多对数的解决方案。
在每一步之后，我们将删除帕累托次优序列。如果一个序列的最后一对被另一个序列的最后一对支配，则一个序列与另一个相同长度的序列相比是次优的。例如，序列 (0, 0)(1, 3) 比 (0, 0)(1, 2) 差。后者为我们提供了更多空间来查找嵌套对，并且我们保证至少可以找到我们为前者找到的所有对。然而，序列 (0, 0)(1, 2) 既不差也不比 (0, 0)(2, 1) 好。我们必须注意的一个小细节是，以退化对结尾的序列总是比以完整对结尾的序列差。
把它们放在一起之后：
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) 最坏的情况，所以你可能不想枚举它们）。
于 2013-09-12T08:17:49.887 回答
2
我相信@Chronical 的答案是错误的，因为它似乎是针对最佳情况，而不是用于计算大 O 复杂性的最坏情况。我欢迎这个证明，但“解决方案”实际上并没有描述一个有效的答案。
KMP 会及时找到匹配的子字符串O(n * 2k)，其中n输入字符串的长度，以及k我们正在搜索的子字符串，但不会O(n)及时告诉您输入字符串中最长的回文数是多少。
为了解决这个问题，我们需要在字符串的末尾找到最长的回文。如果这个最长的后缀回文是长度x，则要添加的最小字符数是n - x. 例如，字符串aaba的最长后缀子字符串是aba有长度的3，因此我们的答案是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在这种情况下n，与简单算法检查每个子字符串所采用的因素相同，因为它以 开始k = n，然后经过k = n - 1，k = n - 2...与简单算法所做的相同。
TL; 博士：
KMP 可以及时告诉您字符串是否是回文O(n)，但这提供了问题的答案，因为您必须检查所有子字符串string[0...end], string[1...end], ..., string[end - 2...end]是否都是回文，从而导致与简单回文检查算法相同（但实际上更糟）的运行时间.
于 2016-08-08T14:36:58.470 回答
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
- 如果它们相同，我们将变量的副本附加
这是算法的基础，直到循环完成。
当循环结束时，最后一次检查是为了确保如果我们得到一个奇数长度的回文，我们将中间的字符附加到新形成的回文的中间。
请注意，如果您决定将相反的字符附加到 string left，则代码中的所有内容都相反；即每次迭代时哪个索引递增，找到匹配时哪个索引递增，打印回文的顺序等。我不想再经历一遍，但你可以试试看。
假设类的 append 方法在恒定时间内运行，此代码的运行复杂度应该是O(N) 。std::string
于 2013-09-11T05:47:02.570 回答
1
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)。如果您想要一种在字符串中的任何位置插入字母以使其成为回文的方法，则此代码不适用于这种情况。
于 2015-02-20T20:57:51.210 回答
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
于 2017-08-02T05:39:01.297 回答
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")
于 2014-07-29T00:14:55.943 回答
0
我假设您无法替换或删除任何现有字符？
一个好的开始是反转一个字符串并在反转的字符串和另一个字符串之间找到最长的公共子字符串 (LCS)。由于这听起来像是一个家庭作业或面试问题，我将把剩下的留给你。
于 2013-09-11T04:33:08.657 回答
0
使用递归
#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);
}
于 2018-06-23T11:47:57.093 回答
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();
}
于 2020-03-24T23:40:21.970 回答
0
// 要附加的字符串以将其转换为回文
public static void main(String args[])
{
String s=input();
System.out.println(min_operations(s));
}
static String min_operations(String str)
{
int i=0;
int j=str.length()-1;
String ans="";
while(i<j)
{
if(str.charAt(i)!=str.charAt(j))
{
ans=ans+str.charAt(i);
}
if(str.charAt(i)==str.charAt(j))
{
j--;
}
i++;
}
StringBuffer sd=new StringBuffer(ans);
sd.reverse();
return (sd.toString());
}
于 2020-09-08T17:21:26.513 回答