首页 > 试题广场 >

回文

[编程题]回文
  • 热度指数：5085 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
京京和东东是好朋友。东东很喜欢回文。回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜,先取定一个字符串s,然后在后面附上 0 个或者更多个字母形成回文,京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。

数据范围：输入的字符串长度满足 ，且保证只含有小写英文字母

输入描述:
输入包括一个字符串s,字符串s长度length


输出描述:
输出一个整数,表示牛牛能够得到的最短的回文长度。
示例1

输入

abab

输出

5

说明

在末尾添加一个 'a' 构成回文
示例2

输入

a

输出

1

说明

本身就是回文
算法知识视频讲解
添加回答
向宇回桌头像 向宇回桌 
import java.util.*;

public class Main {
    private static final int MAX = 50+5;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] arr = sc.next().toCharArray();
        int n = arr.length;
        for (int i=0; i!=n; i++) {
            if (judgePlalindrome(arr, i, n-1)) {
                System.out.println(n+i);
                return;
            }
        }
        return;
    }

    private static boolean judgePlalindrome(char[]a, int i, int j) {
        while (i <= j) {
            if (a[i++] != a[j--]) { return false; }
        }
        return true;
    }
}
发表于 2019-01-27 18:00:15 回复(2)
Smart_Maggie头像 Smart_Maggie 
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
bool huiwen(string s)
{     string s2 = s;     reverse(s2.begin(),s2.end());     if (s2 == s)         return true;     else         return false;
}
int main()
{     string s;     cin >> s;
    if(huiwen(s))//如果s本身就是回文就不需要再添加字母，直接输出s的长度就行
    {
        cout<<s.size()<<endl;
    }
    else
    {
        int i=0;
        for (i = 1; i < s.size(); ++i)         {
            string tmp = s;
            string tmp1 = tmp.substr(0,i);
            reverse(tmp1.begin(), tmp1.end());
            tmp = tmp +tmp1 ;
            if (huiwen(tmp) == true)
            {
                cout << tmp.size() << endl;
                break;
            }                 }
    }         return 0;
}

发表于 2019-05-07 11:52:52 回复(0)
Python
华科平凡头像 华科平凡

python解法

题目中说字符串最大长度小于50，所以可以暴力求解。

直接把长度一个一个往上加，看哪个长度满足条件。

string = input()
for i in range(0, len(string)):
    if string + string[:i][::-1] == (string + string[:i][::-1])[::-1]:
        print(len(string) + i)
        break
编辑于 2019-03-03 23:26:56 回复(0)
ChessC头像 ChessC 
//只能在末尾进行添加
#include <string>
#include <iostream>
using namespace std;
bool judge(string word){
    int lo=0,hi=(int)word.length()-1;
    while(lo<=hi)
        if(word[lo++]!=word[hi--])
            return false;
     return true;
}
int main(){
    string s;
    cin>>s;
    if(judge(s)){ //如果自身就是一个回文串
        cout<<(int)s.length();
        return 0;
    }
    //否则在尾部进行添加
    int i;
    for(i=1;i<(int)s.length();++i){
        if(s[i]==s.back()){ //找第一个可能的最小情况
            if(judge(s.substr(i))){ //如果当前区间内已经是回文，添加i之前的字符即可
                cout<<(int)s.length()+i;
                return 0;
            }
        }
    }
    cout<<2*(int)s.length();
    return 0;
}

发表于 2019-02-22 10:57:48 回复(0)
pein531头像 pein531
这个题是往原字符串的后面添加字符，因此我们只需要考虑从后面截取原字符串能截取的最长回文串有多长。例如：
(1) abacaba，这个字符串本来就是回文串，因此能截取的最长回文串长度为7；
(2) abab，这个字符串从后面能截取的最长回文串为bab（原字符串从下标1开始的后面部分），因此能截取的最长回文串长度为3，只需要在后面添加一个a就能够构成回文串ababa，长度为1+4=5。
根据以上思路不难发现规律：记原字符串为s，我们从下标start=0开始截取后面的子串，如果子串s.substrings(start,s.length())是回文串，那我们在后面添加字符后得到的最短回文串长度应该为start+s.length()。而回文串的判定我们可以采用双指针法。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        int n = str.length();
        int start = 0;
        while(start < n){
            if(isPalindrome(str.substring(start, n))) break;
            start ++;
        }
        System.out.println(start + n);
    }
    
    private static boolean isPalindrome(String str){
        int left = 0, right = str.length() - 1;
        while(left < right){
            if(str.charAt(left) != str.charAt(right))
                return false;
            else{
                left ++;
                right --;
            }
        }
        return true;
    }
}


发表于 2021-02-23 10:20:28 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t;
    cin>>s;
    t = s;
    reverse(t.begin(), t.end());
    int n=s.length();
    for(int i=0;i<n;i++)
        if(s.substr(i, n-i) == t.substr(0, n-i)){
            printf("%d\n", i+n);
            break;
        }
    return 0;
}

发表于 2020-10-05 15:21:22 回复(0)
狂二到狂四之间头像 狂二到狂四之间
以abab为例，你在后面添加a，由于a和a是回文的，你只要判断bab是否回文？
同理，以abcc为例，你在后面添加ba，ba和ab是回文的，你只要判断cc是否回文？
所以在 一个任意字符串 s; 你在后面添加i个字符，由于前i个字符和后面i个字符是回文的，你只要判断从i位置起，长度为s.s.length()-i 的子串是否回文。
#include<iostream>
#include<string>
using namespace std;
int fun(string a);
int main()
{
    string s;
    cin>>s;
    int len=s.length();
    int num=0;//需要添加的字母数
    for (int i=0;i<=len-1;i++)
    {
         if(fun(s.substr(i,len-i)))//判断字符串是否为回文，若不是继续判断其位置i以后的len-i个字符的字串是否回文。
            break;
        num++;
    }
    cout<<num+len;
    return 0;
  
}
//判断是否回文
 int fun(string a)
{
    int len=a.length();
    if(len==1)
     return 1;
    for (int i=0;i<=len/2;i++)
    {
        if(a[i]!=a[len-i-1])
            return 0;
    }
发表于 2019-03-17 17:06:49 回复(5)
Python
专业菜鸟i头像 专业菜鸟i 
#菜鸟出品
s=input()
l=len(s) for i in range(l):
    ss=s+s[:i][::-1]  if ss==ss[::-1]:  print(len(ss))   break

编辑于 2019-03-07 20:23:56 回复(0)
C/C++
刘炳辰头像 刘炳辰 
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
    string s;
    cin >> s;
    int strSize = s.size();
    if(strSize == 1){
        cout << 1 << endl;
        return 0;
    }
    while(strSize < 2 * s.size() - 1){
        if(strSize % 2 == 0){
            //偶数
            int m = strSize / 2;
            int n = m - 1;
            while(n >= 0 && m < s.size()){
                if(s[n] == s[m]){
                    if(n == 0 || m == s.size() - 1){
                        cout << strSize << endl;
                        return 0;
                    }
                    n--;
                    m++;
                }
                else{
                    break;
                }
                
            }
            strSize++;
        }
        else{
            //不为1的奇数
            int m = strSize / 2 + 1;
            int n = strSize / 2 - 1;
            while(n >= 0 && m < s.size()){
                if(s[n] == s[m]){
                    if(n == 0 || m == s.size() - 1){
                        cout << strSize << endl;
                        return 0;
                    }
                    n--;
                    m++;
                }
                else{
                    break;
                }
            }
            strSize++;
        }
    }
    cout << strSize << endl;
    return 0;
}

发表于 2019-02-25 22:16:49 回复(0)
xcTorres头像 xcTorres
#include<iostream>
using namespace std;

bool isPalindrome(string s){
    int start = 0;
    int end = s.size()-1;
    while(start<end){
        if(s[start]!=s[end])
            return false;
        start++,end--;
    }
    return true;
}


int main(){
    
    string s;
    while(cin >> s){
        int n = s.size();
        int maxPali = 1;
        for(int i=0;i<n;i++){
            if(isPalindrome(s.substr(i,n))){
                maxPali = n-i;
                break;
            }
        }
        int res = 2*n-maxPali;
        cout << res << endl;
    }
    return 0;
}

发表于 2018-06-02 10:26:09 回复(0)
Java
Mono_Chrome头像 Mono_Chrome

找寻规律，从i=0开始判断这个改字符到最后一个字符是否是回文串，如果是，字符串长度加上i就是最终结果。

import java.util.Scanner;

public class Main {

    public static boolean isPalindrome(char[] ch, int i, int j) {
        while (i < j) {
            if (ch[i++] != ch[j--]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] ch = sc.next().toCharArray();
        for (int i = 0;  i < ch.length; i++) {
            if (isPalindrome(ch, i, ch.length - 1)) {
                System.out.println(ch.length  + i);
                break;
            }
        }
    }
}
发表于 2019-06-14 16:29:33 回复(0)
李镇强头像 李镇强

python多行 

//最能向后追加的最小长度回文字符串
mystr = input()
n = len(mystr)
if n==1:
    print(1)
else:
    allflag = True //全部相同
    obj = mystr[0]
    dp = [2*n-1]*n
    for index in range(1,n):
        if obj != mystr[index]:
            allflag = False
        if index < n - index - 1:
            continue
        else:
            flag1 = flag2 = True  //奇偶
            for i in range(index+1,n):
                if mystr[i]!=mystr[index-(i-index)]:
                    flag1 = False
                if mystr[i]!=mystr[index-(i-index)+1]:
                    flag2 = False
            mymin = 2*n-1
            if flag1 and 2*index+1 <mymin:
                mymin = 2*index+1
            if flag2 and 2*(index+1)<mymin:
                mymin = 2*(index+1)
            dp[index] = mymin
    if allflag:
        print(n)
    else:
        print(min(dp))


编辑于 2019-04-13 14:52:03 回复(0)
C/C++
当个程序员这么难吗头像 当个程序员这么难吗 
#include<iostream>
#include<sstream>
using namespace std;
bool Palindrome(string& str,int cur_idx)
{
    int sz = str.size()- cur_idx;
    for(int i=0;i<sz/2;++i)
    {
        if(str[i+cur_idx]!=str[cur_idx+sz-i-1]) 
        {
            return false;
        }
    }
    return true;
}
int main()
{
    string str;
    while(cin>>str)
    {
        int sz_origin = str.size();
        int i=0;
        // 判断[i,sz_origin]之间的字符是不是回文
        // 最后的结果为 i+sz_origin
        while(!Palindrome(str,i))
        {
            ++i;
        }
        cout<<i+sz_origin<<endl;
    }
    
    return 0;
}

发表于 2021-04-09 09:11:16 回复(0)
hanscal头像 hanscal
input_s = input()

def findHuiwen(input_s):
    start_idx = len(input_s) //2 
    # even_flag == len(input_s)%2 
    end = len(input_s)
    huiwen_length = 0
    for idx in range(start_idx, end):
        odd_count = even_count = 0
        for i in range(0,end-idx):
            # 比较偶数，
            if input_s[idx+i] == input_s[idx-i-1]:
                even_count +=1
            # 比较奇数
            if input_s[idx+i] == input_s[idx-i]:
                odd_count +=1
        if even_count == end - idx:
            huiwen_length = idx*2 
            break
        if odd_count == end - idx:
            huiwen_length = idx*2 + 1
            break
    print(huiwen_length)

findHuiwen(input_s)

第一层循环从中间开始查找，查询到输入字符串的长度，第二层循环同时逐步比较奇数和偶数，只要有一个条件满足，就可以由当前的idx得到回文长度。
发表于 2020-07-21 09:54:27 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
import java.util.*;
public class Main{
    public static void main(String[] args){
        String s = new Scanner(System.in).nextLine();
        for(int i=0;i<s.length();++i){
            if(check(s.substring(i))){
                System.out.println(i+s.length());
                break;
            }
        }
        
    }
    public static boolean check(String x){
        StringBuffer sb = new StringBuffer(x);
        return x.equals(sb.reverse().toString());
    }
}

编辑于 2020-07-05 15:08:30 回复(0)
C#
乔小妖头像 乔小妖
首先可以写一个判断是否是回文的函数，然后设想，如果本身并不是回文字符串，需要通过添加字母实现回文的话，最好的情况是添加一个字符实现回文，那么这个字符就等于字符串的首字符；如果只需要添加两个字符的话，那么添加的就是字符串的前面的两个字符......这里面隐含的就是：无论额外添加了几个字符，那么这几个字符是与字符串前面相应的字符对应，那么相应删掉前面相应的字符，使剩余字符串为一个回文即可，输出删掉的字符数num，也即添加的字符数，输出（num+原字符串长度）

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace New_journey
{
    class Program
    {
        static void Main(string[] args)
        {
            string s1 =null;
            while (!string.IsNullOrEmpty(s1 = Console.ReadLine()))
            {
                int num = s1.Length;
                for(int i = 0; i < num; i++)
                {
                    if (ishuiwen(s1))
                    {
                        Console.WriteLine(i + num);
                        break;
                    }
                    else
                    {
                        s1 = s1.Substring(1);
                    }
                }
            }   
        }

        static bool ishuiwen(string s)
        {
            int len = s.Length;
            for (int i = 0; i <= len / 2; i++)
            {
                if (s[i] != s[len - 1 - i])
                {
                    return false;
                }
            }
            return true;
        }
    }
}
发表于 2020-05-13 20:08:02 回复(0)
C/C++
海问香12138头像 海问香12138

从加0个字母到加strlen(s)-1个字母暴力枚举就行了 

#include <stdio.h>
#include <string.h>

char s[60];

int main()
{
	int i,j,k,len,flag;
	gets(s);
	len = strlen(s);
	for(i=0;i<len;i++)
	{
		flag = 1;
		char ss[60]={0};
		for(j=0;j<len;j++)
			ss[j] = s[j];
		for(k=i-1;k>=0;k--)
			ss[j++] = s[k];
		for(j--,k=0;j>=k;j--,k++)
			if(ss[j]!=ss[k])
			{
				flag = 0;
				break;
			}
		if(flag)
		{
			printf("%d\n",len+i);
			return 0;
		}
	}
	return 0;
}


发表于 2019-08-22 10:42:22 回复(0)
嘎嘎嘎~头像 嘎嘎嘎~ 
//我说怎么似曾相识，又写了一遍
import java.util.*;
public class Main{
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            Cal(sc);
        }
    }
    public static void Cal(Scanner sc){
        String s=sc.next();
        int i=0;
        for(i=0;i<s.length();i++){
            String t=s.substring(i);
            if(PanDu(t)) break;
        }
        System.out.println(s.length()+i);
    }
    public static boolean PanDu(String s){
        StringBuffer t=new StringBuffer(s);
        t.reverse();
        if(s.equals(t.toString())) return true;
        else return false;
    }
}

//*********************************************************************
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            CAL(sc);
        }
    }
    public static void CAL(Scanner sc){
        String s=sc.next();
        String c="";
        {
        int i=0;
        for (i=0;i<s.length()-1;i++){
            c=c+s.charAt(i);
            c=c+'*';
        }
        c=c+s.charAt(i);
        }
        int j=0;
        for(int i=c.length()/2;i<c.length();i++,j=j+2){
            if (PanDu(c.substring(j,i),c.substring(i+1))){
                break;
            }
        }
        System.out.println(j/2+s.length());
    }
    public static boolean PanDu(String s1,String s2){  StringBuffer cBuffer2=new StringBuffer(s2);  s2=cBuffer2.reverse().toString();
        return s1.equals(s2);
    }

编辑于 2019-07-06 16:16:43 回复(0)
C/C++
韦禹头像 韦禹
//与尾部相等就检查是否构成回文，不构成继续往下->最好O（n）最慢O（n2）
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;cin>>s;
    size_t n=s.size();
    for(size_t i=0;i!=n;++i){
        if(s[i]!=s[n-1]){
            s.insert(s.begin()+n,s[i]);
        }
        else{
            int left=i+1,right=n-2;bool hw=true;
            while(left<right){
                if(s[left]!=s[right]) {hw=false;break;}
                ++left;--right;
            }
            if(hw) break;
            else{
                s.insert(s.begin()+n,s[i]);
            }
        }
    }
    cout<<s.size()<<endl;
    return 0;
}
发表于 2019-06-10 11:01:29 回复(0)
慧哈哈头像 慧哈哈
用马拉松算法，限制回文条件为：回文串一定要包含最后一个字符即可
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
string mk_new(string s) {
    string s_new;
    s_new = "";
    s_new = s_new + "$#";
    for (int i = 0; i < s.length(); i++) {
        s_new = s_new + s[i];
        s_new = s_new + '#';
    }
    s_new = s_new + '\0';
    return s_new;
}

int main() {
    string s,s_new;
    cin >> s;
    s_new = mk_new(s);
    int id = 0;
    int mx = 0;
    int Max_len = -1;
    vector<int> P(s_new.length());
    for (int i = 1; i < s_new.length(); i++) {
        if (i < mx) {
            P[i] = min(P[2 * id - i], mx - i);
        }
        else {
            P[i] = 1;
        }
        while (s_new[i - P[i]] == s_new[i + P[i]]) {
            P[i]++;
        }
        if (mx < i + P[i]) {
            mx = i + P[i];
            id = i;
        }
        if (mx == s_new.length() - 1) {
            Max_len = P[i] - 1;
            break;
        }
    }
    cout<< 2*s.length() -Max_len;
    return 0;
}

发表于 2019-05-10 10:32:02 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 PHP工程师 贪心 模拟 穷举 京东 2018 Java工程师
上传者：小小
难度：
32条回答 9853浏览

热门推荐

通过挑战的用户

查看代码

相关试题

回文

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号