首页 > 试题广场 >

添加回文串

[编程题]添加回文串

热度指数：7570 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个字符串，我们想通过添加字符的方式使得新的字符串整体变成回文串，但是只能在原串的结尾添加字符，请返回在结尾添加的最短字符串。

给定原字符串A及它的长度n，请返回添加的字符串。保证原串不是回文串。

测试样例：

"ab",2

返回："a"

算法知识视频讲解

查看答案及解析

C/C++

kakaan

这是一个讨巧的办法，

问题分解

1、找到最长的回文子串

2、剩余部分就是需要添加的子串

使用Naive查找，寻找最大公共串

这里用到了：翻转子串==原子串 =>回文子串

从原串的开头开始找，比较是否与翻转串的末尾相同

【这里用到了本题的特征：已有的回文子串肯定出现在末尾，不会出现在中间】

Example：

原串 abcdedc

翻转串 cdedcba

    string addToPalindrome(string A, int n) {
        string s = A;
        reverse(s.begin(),s.end()); // 取得翻转串
        for(int i=0;i<n;i++) // Naive查找
             if(A.substr(i,n-i)==s.substr(0,n-i))//求最长公共子串
                return s.substr(n-i,i);//返回公共集后面剩余字符串
        return string("");
    }

发表于 2016-08-30 15:57:03 回复(10)

shizheng

//每次删除掉第一个字符,将这个删除掉的字符放入一个新串中
//如果删除后的字符串是回文串则返回,否则继续第一步
//逆序ans返回
class Palindrome {
    bool judge(string str){
        string tmp = str;
        reverse(tmp.begin(), tmp.end());
        return tmp==str;
    }
public:
    string addToPalindrome(string str, int n) {
        reverse(str.begin(), str.end());
        string ans;
        while (!str.empty()) {
            ans.push_back(str.back());
            str.pop_back();
            if(judge(str))
                break;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

发表于 2016-04-11 23:21:56 回复(3)

牛客398628号

class Palindrome {

public:

bool isP(string s)

{

int low=0;

int high=s.length()-1;

while(low<high)

{

if(s[low]!=s[high])

return false;

low++;

high--;

}

return true;

}

string addToPalindrome(string A, int n) {

// write code here

string s;

int r,low,high;

char temp;

r=n;

while(r>0)

{

s=A.substr(n-r,r);

if(isP(s))

{

s=A.substr(0,n-r);

low=0;

high=s.length()-1;

while(low<high)

{

temp=s[low];

s[low]=s[high];

s[high]=temp;

low++;

high--;

}

return s;

}

r--;

}

};

发表于 2015-09-15 16:47:27 回复(0)

星风雪雨

将字符串反转后求最大交集（原字符从后往前，反转的字符从前往后），反转后的字符串另外部分就是要求的字符串。

String reverse=new StringBuilder(A).reverse().toString();

int sameCount=0;//相同字符数量

for(int i=0;i<A.length();i++){

if(A.charAt(i)==reverse.charAt(sameCount)){

sameCount++;

}else{

if(sameCount>0)

i--;

sameCount=0;

}

return reverse.substring(sameCount);

不过要注意一旦之前有相同的但是某一个不相同了，将索引暂停。

发表于 2016-04-14 21:16:25 回复(0)

北辰1

package ex1;

/**解题思路：

* 1，先判断是否为回文串（正序和倒序顺序一样）（考查字符串的反转）

* 2，若是则返回，若不是则进入第3步

* 3，使用substring()方法，截取字符串，使用for()循环，（第一次，只截取A的第一个字符，然后反转（reserve()方法）），

* 添加进A中，进行判断，若是，则返回，若不是则继续第三步（第2次，截取A的前两个字符，然后反转），添加到A中，进行判断，

* 依次类推。直到满足条件为止

* 4，需要注意的是，此题只输出添加的最小字符，并不是输出回文串，所以要在方法体外定义一个静态变量B,以获取每次反转得到的B,若是

* A是回文串，则返回B

* 注：此题我在想，如果可以使用list链表，因为list.add(index,Parameter)方法，插入的特定位置，后面的数字依次向后

* 挪一位，（比如list(n,A.charAt(i))，第一次往n处插入A中第一个元素，然后判断是否符合回文串，符合返回，否则，第2

* 次往n处插入A中第2个元素，（第一个元素就会被挤到n+1处），然后进行判断，依次类推），但是可能其字符转换太过频繁，所以比较麻烦**/

public class StringRotation {

private static String B = null;

public String addToPalindrome(String A, int n) {

String C=A;

for (int i = 0; i < n; i++) {

if (judge(A)) {

return B;

} else {

B = C.substring(0,i+1);

B=reverse(B);

A=C+B;

}

return null;

}

//实现取得的字符串反转

private String reverse(String b) {

// TODO Auto-generated method stub

char[] a=new char[b.length()];

for(int i=0;i<b.length();i++){

a[i]=b.charAt(b.length()-i-1);

}

return String.valueOf(a);

}

//判断是否为回文串（正序和反序相同时为回文串）

public boolean judge(String A){

char[] a=new char[A.length()];

for(int i=0;i<A.length();i++){

a[i]=A.charAt(A.length()-1-i);

}

String B=String.valueOf(a);

if(A.equals(B)){ //此处不能使用A==B（比较的地址）

return true; //A.equals(B)比较的才是内容

}

return false;

}

public static void main(String args[]){

StringRotation c=new StringRotation();

System.out.print(c.addToPalindrome("abc", 3));

}

发表于 2016-05-29 10:10:34 回复(0)

Python

华科平凡

python solution:

    def addToPalindrome(self, A, n):
        for i in range(1,n+1):
            if A+A[:i][::-1]==(A+A[:i][::-1])[::-1]:
                return A[:i][::-1]

发表于 2017-11-07 19:25:45 回复(1)

夕一啊

//因为只能从最后添加，所以从后往前找，包含最后一个字符的最长回文字串。
//动态规划复杂度也是n方暴力求解也是n方

class Palindrome {
public:
    bool ispalindrome(string A,int start,int end){
   //判断字符串A的区间start到end是否为回文串
        while(start<=end){
            if(A[start]!=A[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
    string addToPalindrome(string A, int n) {
        int i=0,j=0;
       //从头开始找，如果找到当前字符等于最后一个字符，判断这个区间是否为回文串
        for(;i<n-1;i++){
            if(A[i]==A[n-1] && ispalindrome(A,i,n-1))
                break;
        }
	    string result = A;
       //返回的答案为非回文串区间的逆序
        for(;j<i;j++)
            result[j] = A[i-j-1];
        result[j] = '\0';
        return result;
    }
};

编辑于 2017-07-15 22:06:49 回复(0)

kestars

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        // write code here
        StringBuilder temp=new StringBuilder(A);
        String B=temp.reverse().toString();
        for(int i=0;i<A.length();i++){
            String sub1=A.substring(i);
            String sub2=B.substring(0,n-i);
            if(sub1.equals(sub2) && !sub1.equals(""))
                return new StringBuilder(A.substring(0,i)).reverse().toString();
        }
        return new StringBuilder(A).toString();
    }
}

发表于 2018-10-12 13:23:19 回复(0)

Python

TimeMac

#把字符串拆成两部分
#例如abcdd：从a,bcdd查找右边的是否为回文串，如果不是则再向右移动切割
#         然后ab,cdd查找
#       再然后abc，dd查找到dd为回文串，逆序返回此时左边的字符串（cba）。
#所以最大一定先找到被返回

class Palindrome:
    def addToPalindrome(self, A, n):
        if n == 2:
            return A[0]
        for i in range(1,n):    #从开头一个一个查找剩余的字符串是否为回文串
            temp = A[i:]
            if temp == temp[::-1]:
                return A[i-1::-1]

编辑于 2018-09-23 11:17:35 回复(0)

吾生有你

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        // write code here
        int index=0;
        for(int i=0; i<n; i++){  
            int left=i;         //定义俩指针
            int right=n-1; 
            while(left<=right){   //判断俩指针之间是否为回文串
                if(A.charAt(left)==A.charAt(right)){
                    left++;
                    right--;
                }else
                    break;
            }
            if(left-right==1 || left-right==2){  //如果俩指针之间为回文串，则返回头指针
                index=i;
                break;
            }
        }
        StringBuilder str=new StringBuilder(A.substring(0, index));  //做发转字符串
        return str.reverse().toString();
    }
}

发表于 2018-06-28 19:57:19 回复(0)

C/C++

nbgao

class Palindrome {
public:
    string addToPalindrome(string A, int n) {
        string s = A;
        reverse(s.begin(), s.end());
        for(int i=0;i<n;i++)
        {
            if(A.substr(i,n-i)==s.substr(0,n-i))
                return s.substr(n-i,i);         }         return "";
    }
};

发表于 2017-11-04 01:12:30 回复(0)

324134134143428

//怎么说呢，1、找到方向-----动规-----

	原串      str1 = abcdedc



	翻转串       str2 = cdedcba



	



	便利str1 找到一个i，使得从i到最后（一共n-i-1个），然后和str2的前n-i-1个相同。



	 



	 



	if(str1.substr(i,n-i)==str2.substr(0,n-i)) 
      return str2.substr(n-i,i); 



	最长子串？？？？？可能吧。



	符代码如下：



	class Palindrome {
public:
    string addToPalindrome(string A, int n) {
        string s = A;int num_diff;
        string S = "";
        reverse(s.begin(),s.end());
        for(int i = 0;i<n;i++)
            if(A.substr(i,n-i)==s.substr(0,n-i)) 
                return s.substr(n-i,i);
        return S;
    }
};

发表于 2017-11-01 17:41:34 回复(0)

素瑾

1 找出原串中以原串最后一个字符结尾的最长的回文串（的长度）
1.1 dp[i][j]代表i到j回文串的长度，如果不是回文串为0
1.2 当a[i]==a[j]的时候更新dp[i][j]
1.3 取最值：只用取以原串最后一个字符结尾的回文串
2 截取1找出的回文串之前的子串
import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        // write code here
        int[][] dp = new int[n][n];
        int max = 1;

//1
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        char[] a = A.toCharArray();
        
      
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(j-1>=0&&a[i]==a[j]
                   &&(j==i+1||dp[i+1][j-1]!=0))
                    dp[i][j] = 2+dp[i+1][j-1];
                if(dp[i][j]>max && j==n-1)
                    max=dp[i][j];
            }
        }       
    //2    
        return new StringBuilder(A.substring(0, n - max)).reverse().toString();
    }
}

编辑于 2017-08-10 15:48:11 回复(0)

Java

JustYoung

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        // write code here
        char[] cs = A.toCharArray();
        int i = 0;
        int j = n - 1;
        int index = -1;
        while (i <= j) {
            if (cs[i] == cs[j]) {
                ++i;
                --j;
            } else {
                if (j == n - 1)
                    ++i;
                j = n - 1;
                index = i;
            }
        }
        if (index == -1)
            return "";
        else {
            return new StringBuilder(A.substring(0, index)).reverse().toString();
        }
    }
}

发表于 2016-09-23 13:18:51 回复(0)

Java

foresee

public String addToPalindrome(String A, int n) {

        char[] a = A.toCharArray();
        int answer = 0;
        String str = "";
        boolean flag = true;
        for(int i = 0;i < a.length - 1;i++){
            flag = true;
            if(a[a.length - 1] != a[i]){
                   answer ++;
               }else{
                for(int j = 1;j < a.length - i;j++){
               		if(a[a.length - j - 1] != a[i + j]){
                        answer++;
                        flag = false;
                        break;
                    } 
           		}
                if(flag == true){
                 break;   
                }
            }
        }
        for(int x = answer - 1;x >= 0;x--){
            str += a[x];
        }
        return str;
    }

发表于 2016-08-01 16:20:02 回复(0)

牛客703246号

# -*- coding:utf-8 -*-
class Palindrome:
    def addToPalindrome(self, A, n):
        # write code here
        i=0
        while i<=n:
            if A+A[i::-1]==(A+A[i::-1])[::-1]:
                return A[i::-1]
            i+=1          
f=Palindrome()
print f.addToPalindrome('abcd',4)

发表于 2016-05-14 07:14:59 回复(0)

czt

class Palindrome

{

public:

string addToPalindrome(string A, int n)

{

string B;

string C;

int i = 0,j = 0;

int k = 0;

for(i = 0;i < n;i++)//不断的将字符串中的字符一次在中间插入；

{

C.push_back(A[i]);

A.insert(n,C);

C = "";

if(test(A))//判断插入之后的字符串是否是回文

{

break;

}

for(i = n;i < A.size();i++)

{

B.push_back(A[i]);

}

return B;

// write code here

}

bool test(string T)//判断字符串是否是回文结构

{

int i = 0,j = 0;

for(i = 0;i < T.size();i++)

{

j = T.size()-1-i;

if(i > j)

{

break;

}

if(T[i]!=T[j])

{

return false;

}

return true;

}

};

发表于 2016-05-08 14:00:02 回复(0)

只欠东风

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        // write code here
        String returnStr=A.charAt(0)+"";
        String temp;
        for(int i=1;i<A.length();i++){
            temp=A.substring(i,A.length());
            
            if(checkIsHW(temp)){
                break;
            }
            returnStr=A.charAt(i)+returnStr;
        }
        
        return returnStr;
    }
    //判断是否是回文
    public boolean checkIsHW(String substr){
        if(substr.length()<=1){
            return true;
        }
        int length=substr.length();
        for(int i=0;i<length/2;i++){
            if(substr.charAt(i)!=substr.charAt(length-i-1)){
                return false;
            }
        }
        return true;
    }
}

发表于 2016-04-18 13:46:50 回复(0)

C/C++

求工作555

//求公共子串思路不对

发表于 2019-08-21 11:31:46 回复(0)

Dayanghe

对比较A和A的反序，从A[i:]比较公共序列中最大回文字符串，则A[:i]的反序应该添加在A的末尾

class Palindrome:
    def addToPalindrome(self, A, n):
        # write code here
        for i in range(n):
            if A[i:] == A[::-1][:n-i]:
                return A[:i][::-1]

发表于 2019-07-15 22:22:07 回复(0)