首页 > 试题广场 > 添加回文串
[编程题]添加回文串
  • 热度指数:7257 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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

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

测试样例:
"ab",2
返回:"a"
这是一个讨巧的办法,
问题分解
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)
//每次删除掉第一个字符,将这个删除掉的字符放入一个新串中
//如果删除后的字符串是回文串则返回,否则继续第一步
//逆序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)
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)
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)
将字符串反转后求最大交集(原字符从后往前,反转的字符从前往后),反转后的字符串另外部分就是要求的字符串。
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)
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 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)
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)
#把字符串拆成两部分
#例如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 回复(1)
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)
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)
//怎么说呢,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)
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)
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)
# -*- 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头像 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)
//求公共子串思路不对
发表于 2019-08-21 11:31:46 回复(0)

对比较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)