首页 > 试题广场 >

回文数索引

[编程题]回文数索引

热度指数：6602 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个仅由小写字母组成的字符串。现在请找出一个位置，删掉那个字母之后，字符串变成回文。请放心总会有一个合法的解。如果给定的字符串已经是一个回文串，那么输出-1。

输入描述:

第一行包含T，测试数据的组数。后面跟有T行，每行包含一个字符串。

输出描述:

如果可以删去一个字母使它变成回文串，则输出任意一个满足条件的删去字母的位置（下标从0开始）。例如：

bcc

我们可以删掉位置0的b字符。

示例1

输入

3
aaab
baa
aaa

输出

3
0
-1

算法知识视频讲解

Bostonpigeons

#include<iostream>

#include<bits/stdc++.h>
#include<cstring>
usingnamespacestd;
string s;
intjudge(inta){
string s1;
for(inti=0;i<s.length();i++){
if(i==a) continue;
s1+=s[i];
}
//   cout<<s1<<endl;
for(inti=0;i<=s1.length()/2;i++){
if(s1[i]!=s1[s1.length()-i-1]) return0;
}
cout<<a<<endl;
return1;
}
intmain()
{
intn;
cin>>n;
//string s;
for(inti=0;i<n;i++){
cin>>s;
if(judge(-1)) continue;
for(intj=0,k=s.length()-1;j<=(s.length()/2);j++,k--){
if(s[j]!=s[k]){
if(!judge(j)) cout<<k<<endl;
break;
}
}
}
return0;
}

编辑于 2019-06-13 23:12:05 回复(0)

txy_钟琛

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int nums = scanner.nextInt();
        while (nums > 0) {
            StringBuilder str = new StringBuilder(scanner.next());
            int start = 0;
            int end = str.length() - 1;
            int ans = -1;
            while (start < end) {
                if (str.charAt(start) != str.charAt(end)) {
                    boolean flag = IsPalindrome(start+1,end ,str);
                    if (flag){
                        ans = start;
                        break;
                    }else {
                        ans = end;
                        break;
                    }
                }
                start++;
                end--;
            }
            System.out.println(ans);
            nums--;
        }
    }

    private static boolean IsPalindrome(int start, int end, StringBuilder str) {
        while (start < end) {
            if (str.charAt(start) != str.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }       
}

发表于 2022-05-28 10:58:18 回复(0)

picklemanrick

def get_whether_Ustr(temp_str):
    temp_list = list(temp_str)
    if temp_list == list(reversed(temp_list)):
        return -1
    return 0
n = int(input())
for i in range(n):
    str = input()
    if get_whether_Ustr(str) == -1:
        print(-1)
        continue
    for ind,chr in enumerate(str):
        temp_str = str[:ind]+str[ind+1:]
        if get_whether_Ustr(temp_str) == -1:
            print(ind)
            break

发表于 2022-01-10 02:38:45 回复(0)

Java

lmz9509

/*
思路：回文数函数，每次去掉一个数后进行判断
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i = 0;i<N;i++){
            String str = br.readLine();
            if(isHui(str)){
                System.out.println(-1);
                continue;
            }else{
                for(int j = 0;j<str.length();j++){
                    if(j==0){
                        String newstr = str.substring(1);
                        if(isHui(newstr)){
                            System.out.println(j);
                            break;
                        }
                    }else if(j== str.length()-1){
                        String newstr = str.substring(0,j);
                        if(isHui(newstr)){
                            System.out.println(j);
                            break;
                        }
                    }else{
                        String newstr = str.substring(0,j) + str.substring(j+1);
                        if(isHui(newstr)){
                            System.out.println(j);
                            break;
                        }
                    }
                }
            }
        }
    }
    
    public static boolean isHui(String str){
        if(str.length()<=1)return true;
        int left = 0,right = str.length()-1;
        while(left<right){
            if(str.charAt(left) == str.charAt(right)){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }
}

发表于 2020-05-20 16:27:22 回复(0)

初心者托奇

for i in range(int(input())):
    a = input()
    for i in range((len(a) - 1) // 2):
        if a[i] != a[len(a) - i - 1]:
            print(i if a[i + 1] == a[len(a) - i - 1] else len(a) - i - 1)
            break
    else:
        print(-1)

发表于 2020-03-16 18:05:04 回复(0)

小蝌蚪666

#include <iostream>
using namespace std;
int main(void){
    string s;
    int T;
    cin>>T;
    while(T--){
        cin>>s;
        string r(s.rbegin(), s.rend());
        int i, len = s.length(), res = -1;
        for(i = 0; i < len; ++i){
            if(s[i] != r[i]){
                res = (s[i] == r[i+1]) ? len-i-1 : i;
                break;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

回文字符串的特点是正向反向输出都是一样的，利用这个特点，每次读取一个字符串s，将其反转得到新的字符串r，再从下标0开始逐个比较s，r，如果遇到s[i]不等于r[i]，说明在这个位置上出现了那个唯一的干扰字符，但是注意，这个并不是最终的答案！！！

以abb为例，反转之后得到bba，进行比较得到i=0时s[i]='a'不等于r[i]='b'，这个时候把abb中0位置的a去掉得到bb是回文没问题，但如果一开始的字符串是bba呢？比较的结果还是i=0，但是答案应该是2！出现这个问题的原因在于不能确定插入的干扰字符是在原来回文字串的左边部分还是右边部分，这个时候要看s[i]和r[i+1]的关系，如果s[i]不等于s[i+1]，说明插入干扰字符在回文串的左边，也就是正确答案就是i，否则的话正确答案应该是i在以字符串中心对称的位置len-i-1

编辑于 2019-08-23 17:20:53 回复(2)

LongXiaJun

"""
1. 首先排除回文串情况
2. 处理每个字符串，两个前后指针，判断是否相等，如果不相等，判断x[i+1]与x[j]相等，则删除i，反之如果x[i]与x[j-1]相等，则删除j
"""


n = int(input().strip())

def func(x):
    if x == x[::-1]:
        return -1
    else:
        j = len(x) - 1
        for i in range(len(x)):
            if x[i] != x[j]:
                if x[i] == x[j-1]:
                    return j
                elif x[i+1] == x[j] :
                    return i
            j -= 1
                

for i in range(n):
    line = input().strip()
    print(func(line))

发表于 2019-08-01 15:32:39 回复(1)

张小公爷

#include<bits/stdc++.h>
using namespace std;
string aa;
int main()
{
int line,len,i,k,j;
int count,cas;
cin>>line;
    count=0;
for(k=0;k<line;k++)
{
cin>>aa;
len=aa.length();
for(i=0,j=len-1;i<j;i++,j--)
      {
      if(aa[i]==aa[j]) cas=-1;
      else
      {
if(aa[i]==aa[j-1]) cas=j;
else cas=i;
      break;
      }
      }
if(cas==-1) printf("-1\n");
else printf("%d\n",cas);
}
}

发表于 2019-07-26 21:39:02 回复(0)

天启ddd


	#include <bits/stdc++.h>



	usingnamespacestd;



	boolcal(string s,intindex){



	    vector<char> a,b;



	    auto ite=s.begin();



	    s.erase(ite+index);



	    intn=s.size();



	    if(s[0] != s[n-1]) returnfalse;



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



	        a.push_back(s[i]);



	        b.push_back(s[n-i-1]);



	    }



	    returna==b;



	}



	boolcal(string s){



	    vector<char> a,b;



	    intn=s.size();



	    if(s[0] != s[n-1]) returnfalse;



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



	        a.push_back(s[i]);



	        b.push_back(s[n-i-1]);



	    }



	    returna==b;



	}



	intmain(void){



	    vector<int> res;



	    intn=0;



	    cin>>n;



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



	        string s;



	        cin>>s;



	        intn=s.size();



	        if(cal(s)){



	            res.push_back(-1);



	            continue;



	        }



	        for(intj=0;j<n;++j){



	            if(cal(s,j)){



	                res.push_back(j);



	                break;



	            }



	        }



	    }



	    for(inti=0;i<res.size();++i){



	        cout<<res[i]<<endl;



	    }



	    return0;



	}

发表于 2019-06-26 14:26:12 回复(0)

加油加油(ง•̀..•́)ง

#include<string>
#include<iostream>
using namespace std;
bool FlagError = false;
int isHW(string str,int left,int right)//回文数判断
{
    while(left < right)
    {
        if(str[left]==str[right])
        {
            left ++;
            right --;
        }
        else if(!FlagError)
        {
            FlagError = true;
            if(isHW(str,left+1,right)!=-2)
            {
                return left;
            }
            else if(isHW(str,left,right-1)!=-2)
            {
                return right;
            }
        }
        else
            return -2;//无法纠正
    }
    return -1;//输入原本就是一个回文串
}
int main()
{
    int num = 0;
    string str;
    cin>>num;
    while(num--)
    {
        FlagError = false;
        cin>>str;
        cout<<isHW(str,0,str.size()-1)<<endl;
    }
    return 0;
}

发表于 2019-06-09 14:48:28 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int T;
    cin>>T;
    while(T--){
        cin>>s;
        int l = s.length(), p=-1;
        string t(s.rbegin(), s.rend());
        for(int i=0;i<l;i++)
            if(s[i]!=t[i]){
                p = (s[i]==t[i+1])?l-i-1:i;
                break;
            }
        cout<<p<<endl;
    }
    return 0;
}

发表于 2019-11-03 01:22:21 回复(0)

C++

一个达布刘

#include <iostream>
#include <type_traits>
using namespace std;
bool IsHuiwen(string &s,int *start,int *end)
{
    int i=0;
    int j=s.size()-1;
    bool flag=true;
    while (i<=j)
    {
        if(s[i]!=s[j])
        {
            flag=false;
            break;
        }
        i++;
        j--;
    }
    if(start!=nullptr)
    *start=i;
    if(end!=nullptr)
    *end=j;
    return flag;
}

int main() {
    int num;
    cin>>num;
    string s;
    while (num) 
    {
        cin>>s;
        int start=0;
        int end=s.size();
        if(IsHuiwen(s,&start,&end))
        {
            cout<<-1<<endl;
        }
        else
        {
            s.erase(end,1);
            if(IsHuiwen(s,nullptr,nullptr))
            {
                cout<<end<<endl;
            }else {
                cout<<start<<endl;
            }
        }
        num--;
    }
}

发表于 2023-05-30 13:35:41 回复(0)

C++

爱米信米等米12139

bool isR(vector<char>& str) { //判定是否是回文串

vector<char> cpy(str);

reverse(cpy.begin(), cpy.end());

if (cpy == str) {

return true;

}

return false;

}

int main() {

int n;

cin >> n;

while (n--) { //一个一个来判定

string s;

cin >> s;

vector<char> str(s.begin(), s.end());

if(isR(str)) //刚开始是否为回文串

{

cout<<-1<<endl;

continue; //继续

}

for (int i = 0; i < str.size(); i++) {

vector<char> nstr(str);

nstr.erase(nstr.begin()+i); //一个一个删来试一试

if(isR(nstr))

{

cout<<i<<endl;

break;

}

发表于 2022-10-09 22:15:38 回复(0)

Python

赵哈哈·

def repair(s):
    s = [i for i in s]
    if s == s[::-1]:
        return -1
    n = len(s)
    mask = [True for _ in range(n)]
    for i in range(n):
        mask[i] = False
        tmp = [s[j] for j in range(n) if mask[j]]
        if tmp == tmp[::-1]:
            return i
        mask[i] = True

a = int(input())
b = []
for i in range(a):
    b.append(input())
for j in b:
    print(repair(j))

发表于 2022-08-05 13:29:00 回复(0)

Bitdancing

#include<iostream>
#include<string>
using namespace std;

bool IsHuiwen(string& str, int& start, int& end, int flag)
{
if(str.size() == 0)
return true;

int i = 0;
int j = str.size()-1;
bool result = true;

while(i < j)
{
if(str[i] != str[j])
{
result = false;
break;
}
++i;
--j;
}

// 不是回文
if(result == false && flag == 1)
{
start = i;
end = j;
}
return result;
}

int main()
{
int t;
cin >> t;
while(t--)
{
string str;
cin >> str;

int start = 0;
int end = str.size()-1;
// 判断是否是回文
if(IsHuiwen(str, start, end, 1))
{
cout << -1 << endl;
continue;
}
// 删去start下标位置的字符
str.erase(start, 1);
// 判断是否是回文串
if(IsHuiwen(str, start, end, 0))
{
cout << start << endl;
continue;
}
else
{
cout << end << endl;
}
}
return 0;
}

发表于 2022-04-30 13:41:45 回复(0)

Python

牛客758087690号

n=int(input())
for i in range(0,n):
    arr=list(map(str,input()))
    l=len(arr)
    pos=0
    while len(arr)>1:
        if arr[0]==arr[-1]:
            arr.pop(0)
            arr.pop()
            pos+=1
            if len(arr)==1:
                print(-1)
                break
        else:
            if len(arr)==2:
                print(pos+1)
                break
            if arr[0]==arr[-2]:
                pos=l-pos-1
                print(pos)
                break
            if arr[1]==arr[-1]:
                print(pos)
                break

编辑于 2021-03-26 21:16:40 回复(0)

晴天的枫

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = Integer.parseInt(sc.nextLine());
        int j = 0;
        while (j < i) {
            String s = sc.nextLine();
            if (checkHuiWen(s)) {
                System.out.println(-1);
            } else {
                for (int k = 0; k < s.length(); k++) {
                    boolean b = checkHuiWen(s.substring(0, k) + s.substring(k+1));
                    if (b) {
                        System.out.println(k);
                        break;
                    }
                }
            }
            j++;
        }
    }

    /**
     * 检查是否是回文
     **/
    private static boolean checkHuiWen(String s) {
        if (s == null || s.equals("")) return false;
        int length = s.length();
        int mid = length / 2;
        int end = length - 1;
        for (int i = 0; i < mid; i++) {
            if(s.charAt(i) != s.charAt(end - i)) {
                return false;
            }
        }
        return true;

    }
}

发表于 2020-10-09 13:06:11 回复(0)

C/C++

牛客549207409号

#include<iostream>
#include<algorithm>
#include<string>
int main()
{
int n;
std::string s;
while(std::cin>>n)
{
for(int i=0;i<n;i++)
{
std::cin>>s;
std::string t=s;
reverse(t.begin(),t.end());
if(t==s)std::cout<<-1<<std::endl;
else
{
for(int j=0;j<s.size();j++)
{
std::string u=s;
u.erase(j,1);
t=u;
reverse(t.begin(),t.end());
if(t==u)
{
std::cout<<j<<std::endl;
break;
}
}
}
}

}
return 0;
}

发表于 2020-09-19 12:55:12 回复(0)

C/C++

一城烟雨柳色青

//思路：双指针
#include<iostream>
#include<string>
using namespace std;

int f(string& s)
{
    int i,j;
    for(i = 0,j = s.size()-1; i < j; ++i,--j)
    {
        if(s[i] != s[j])
        {
            if(i + 1 < s.size() && s[i + 1] == s[j])        //说明i是不匹配的
                return i;
            else if(j - 1 >= 0 && s[i] == s[j - 1])  //说明j不匹配
                return j;
        }
    }
    if(s.size()/2 != 0 && s[i] != s[j])   //奇数,偶数个不存在出来不相等
        return i;
    return -1;
}
int main()
{
    int put;
    while(cin >> put)
    {
        for(int i = 0; i < put; ++i)
        {
            string s;
            cin >> s;
            cout << f(s) << endl;
        }
    }
    return 0;
}

发表于 2020-08-09 22:13:10 回复(0)

zarme

先从外向内找到不对称的两个字符的位置，再决定去掉这两个字符中的哪一个以后内部也是对称的。

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        char[] str;
        int left,right;//当前比较的字符的下标
        for(int i=0;i<n;i++){
            str=sc.next().toCharArray();
            left=0;
            right=str.length-1;
            int res=-1;
            while(left<right){
                if(str[left]!=str[right]){
                    //left和right中有一个破坏了回文
                    if(isNotHuiwen(str,left,right-1)){
                        res=left;
                    }
                    else{
                        res=right;
                    }
                    break;
                }
                left++;
                right--;
            }
            System.out.println(res);
        }
    }
    public static boolean isNotHuiwen(char[] str,int left,int right){
        while(left<right){
            if(str[left]!=str[right]){
                return true;
            }
            left++;
            right--;
        }
        return false;
    }
}

发表于 2020-07-23 17:34:48 回复(0)