首页 > 试题广场 >

回文字符串

[编程题]回文字符串
  • 热度指数:4120 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
回文字符串就是正读和反读都一样的字符串,如“viv”、“nexen”、“12321”、“qqq”、“翻身把身翻” 等。
给定一个非空字符串 str,在最多可以删除一个字符的情况下请编程判定其能否成为回文字符串;如果可以则输出首次删除一个字符所能得到的回文字符串,如果不行则输出字符串 "false" 。

输入描述:
一个非空字符串



输出描述:
一个回文字符串,或者 "false" 字符串(如果无法构造出回文字符串的话)
示例1

输入

abda

输出

ada

说明

删除字符串"abda"中的一个字符 ‘b’ 后,得到 "ada"是一个回文字符串;删除一个字符 ‘d’ 后,得到 "aba"也是一个回文字符串;所以最终输出为 "ada"。

备注:
1、输入仅包含数字或字母;
2、当分别删除不同的字符后,均可得到回文字符串时,输出首次删除一个字符所得到的回文字符串;若无法构造出回文字符串,则输出字符串false;
import java.util.*;
public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int i=0,j=s.length()-1;
        String res = "";
        //此题必须要删除一个字符
        //本身是回文字符串的要输出删除一个字符的结果
        if(isValid(s,0,s.length()-1)==true){
             res = s.substring(1,s.length());
             System.out.print(res);
             return;
        }
        while(i < j){
            if(s.charAt(i) != s.charAt(j)){
                if(isValid(s,i+1,j)){
                    res += s.substring(0,i);
                    res += s.substring(i+1,s.length());
                    System.out.print(res);
                    return;
                }
                else if(isValid(s,i,j-1)){
                    res += s.substring(0,j);
                    res += s.substring(j+1,s.length());
                    System.out.print(res);
                    return;
                }
                else{
                    System.out.print("false");
                    return;
                }
            }
            
            i++;
            j--;
            
        }
    }
    public static boolean isValid(String s,int i,int j){
        while(i < j){
            if(s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

发表于 2021-06-16 21:54:40 回复(0)
def isHuiWen(word):
    left,right = 0,len(word)-1
    while left<right:
        if word[left] != word[right]:
            return False
        left += 1
        right -= 1
    return True


if __name__ == "__main__":
    word = input()
    wordNum = len(word)
    flag = False
    wordCopy = word[1:]
    if isHuiWen(word):
        print(wordCopy)
        flag = True
    else:
        for i in range(1,wordNum):
            wordCopy = word[:i] + word[i+1 :]
            if isHuiWen(wordCopy):
                print(wordCopy)
                flag = True
                break
    if not flag:
        print("false")

发表于 2021-04-11 14:59:33 回复(0)
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为80.00%
用例:
vvvvvvvvvvvvvvvvvvv
对应输出应该为:
vvvvvvvvvvvvvvvvvv
你的输出为:
vvvvvvvvvvvvvvvvvvv

给我整不会了
发表于 2021-03-31 16:37:12 回复(10)
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
bool judge(string a){
    int i=0;
    while(i<floor(a.length()/2)){
        if(a[i]!=a[a.length()-1-i])return false;
        i++;
    }
     return true;   
}
int main(){
    string input;
    cin>>input;

    for (int i=0;i<input.length();i++){
        string temp_input(input);
        temp_input.erase(i,1);
        if (judge(temp_input)){
            cout<<temp_input<<endl;
            return 0;
        }
    }
    cout<<"false"<<endl;
    return 0;
}

发表于 2021-06-16 22:53:41 回复(1)
顺序去排除字符串的某个字符,利用双指针对剩余字符组成的字符串进行回文性的判断,输出第一个回文串即可。
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();
        for(int i = 0; i < str.length(); i++){
            if(isPalindromic(str, i)){
                System.out.println(str.substring(0, i) + str.substring(i + 1));
                return;
            }
        }
        System.out.println("false");
    }
    
    private static boolean isPalindromic(String str, int excludePos) {
        int left = 0, right = str.length() - 1;
        while(left < right){
            if(left == excludePos) left ++;
            if(right == excludePos) right --;
            if(str.charAt(left) == str.charAt(right)){
                left ++;
                right --;
            }else{
                return false;
            }
        }
        return true;
    }
}

编辑于 2021-07-25 08:46:41 回复(0)
双指针 i、j分别从头尾开始。若t[i]==t[j] i++ j--;count计数
若不相等,i前移或者j后移,若相等继续走下去;最后若count>=2 直接false;
若两者都不相等,直接输出 false;
#include<iostream>
using namespace std;

int main(){
    string t;
    cin>>t;
    int i=0;
    int j=t.size()-1;
    int flag=0;
    int count=0;
    while(i<=j){
        if(t[i]==t[j]){
            i++;j--;
        }
        else{
            if(t[i+1]==t[j]){
                t.erase(i,1);
                i++;
                count++;
                continue;
            }
            else if(t[i]==t[j-1]){
                t.erase(j,1);
                j--;
                count++;
                continue;
            }
            else{
                cout<<"false"<<endl;
                return 0;
            }
        }
    }
    if(count>1){
        cout<<"false"<<endl;
    }
    else{
        if(count==0){
            t.erase(i-1, 1);
        }
        cout<<t<<endl;
    }
    return 0;
}


发表于 2021-06-10 15:49:52 回复(2)
说实话不理解为什么全是回文的话,仍然要删除第一个,没注意这个细节卡了半小时
```` 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        String input=scanner.next();
        String res= helper(input);
        System.out.print(res);
        
    }
    
    public static String helper(String s){
        if(s.length()<1){
            return "false";
        }
        if(ispalidrom(s)){
            return s.substring(1,s.length());
        }
        
        int i=0,j=s.length()-1;
        StringBuilder sb=new StringBuilder(s);
        while(i<j){
            if(s.charAt(i)!=s.charAt(j)){
                
                if(ispalidrom(s.substring(i,j))){
                    return sb.deleteCharAt(j).toString();
                }
                else if(ispalidrom(s.substring(i+1,j+1))){
                    return sb.deleteCharAt(i).toString();
                }
                else{
                    return "false";
                }
            }
            i++;
            j--;
        }
        return "false";
        
    }
    private static boolean ispalidrom(String s){
        
        int i=0,j=s.length()-1;
        while(i<j){
            if(s.charAt(i)!=s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    
}
````

发表于 2022-04-21 00:43:46 回复(0)
def func(a):
    le, ri = 0, len(a) - 1
    loc = 0
    flag = 0
    while le < ri:
        if a[le] == a[ri]:
            le += 1
            ri -= 1
        else:
            flag += 1
            if flag > 1:
                return "false"
            if a[le+1] == a[ri]:
                loc = le
                le += 1
            elif a[le] == a[ri-1]:
                loc = ri
                ri -= 1
            else:
                return "false"
    if loc == 0:
        return a[1:]
    else:
        return a[:loc] + a[loc+1:]

发表于 2023-10-25 11:24:39 回复(0)
#include "bits/stdc++.h"

using namespace std;

string del(string input, int x) {
    string ans;
    for (int i = 0; i < input.size(); i++) {
        if (i != x) {
            ans.push_back(input[i]);
        }
    }
    return ans;
}

bool f(string input) {
    int n = input.size();
    if (input.size() % 2 == 0) {
        for (int i = 0; i < n / 2; i++) {
            if (input[i] != input[n - 1 - i]) {
                return false;
            }
        }
    } else {
        for (int i = 0; i < n / 2; i++) {
            if (input[i] != input[n - 1 - i]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    string input;
    cin >> input;
    int n = input.size();
    for (int i = 0; i < n; i++) {
        string tmp = del(input, i);
        if (f(tmp)) {
            cout << tmp << endl;
            return 0;
        }
    }
    cout<<"false"<<endl;
    return 0;
}
//
//if (input.size() == 1 || f(input)) {
//cout << input << endl;
//return 0;
//} else {
//
//}
//cout << false << endl;
哈哈哈哈蚌埠住了,我以为是我中文的处理的问题,结果发现是题目明明说的最多删除一个元素,结果代码是要仅删除一个,一改就过,我还在怀疑是不是我有什么大病。
发表于 2022-09-14 12:08:45 回复(0)
#include<iostream>
using namespace std;
#include<vector>
bool ishuiwen(string str,int low,int high){
    for(int i=low,j=high;i<j;i++,j--){
        if(str[i]!=str[j]) return false;
    }
    return true;
}
int main(){
     string str;cin>>str;
     int n=str.size();
     int left=0;int right=n-1;
     while(left<right){
         if(str[left]==str[right]){
             left++;right--;
         }
         else{  // 遇到不相等的
             bool deleteleft=ishuiwen(str, left+1, right);
             bool deleteright=ishuiwen(str, left, right-1);
             if(deleteleft==false&&deleteright==false) {
                 std::cout<<"false";
                 return 0;
             }
             if(deleteleft){
                 str.erase(left,1);std::cout<<str;
                 return 0;
             }
             else if(deleteright){
                 str.erase(right,1);std::cout<<str;
                 return 0;
             }
             else if(deleteleft&&deleteright){
                 str.erase(left,1);std::cout<<str;
                 return 0;
             }
         }
     }
     str.erase(left,1);std::cout<<str;  // 按题意 必须要删除一个
    
    return 0;
 }

发表于 2022-04-06 12:00:52 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int l = str.length();
        int i = 0;
        while(i < l) {
            String newStr = removeCharAt(str, i);
            //System.out.println(newStr);
            String reverse = new StringBuffer(newStr).reverse().toString();
            //System.out.println(reverse);
            if(newStr.equals(reverse)) {
                System.out.println(newStr);
                break;
            }
            else {
                i++;
                if(i >= l) {
                    System.out.println("false");
                }
            }
            }
    }
    
    public static String removeCharAt(String s, int pos) {
        return s.substring(0, pos) + s.substring(pos + 1);
     }
发表于 2021-11-04 10:34:53 回复(0)
import java.util.*;
public class Main {
	public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        StringBuffer S = new StringBuffer(in.nextLine());
        int n = S.length();
        for(int i=0;i<n;i++) {
            // 根据JAVA字符串的特性,不能直接StringBuffer t = S;
            StringBuffer t = new StringBuffer(S);
            String s = t.deleteCharAt(i).toString(); // 删掉当前字符
            if(Judge(s)) {                           // 判断删掉一个字符后的字符串是否为回文串
                System.out.println(s);
                return;
            }
        }
        // 题目要求的是以“删除一个字符后能构成回文串”为优先条件,所以原字符串要在后面判断
                                    // 当删掉一个字符的所有情况都不符合回文串时
        if(Judge(S.toString())) {   // 判断最开始输入的字符串是否符合回文串
        	System.out.println(S);
        	return;
        }
        System.out.println(false);  // 以上两种情况都不符合,输出false
	}
    // ---------------------------------------------------------------------------------
	public static boolean Judge(String s) { // 判断当前字符串是否为回文串
		int n = s.length();
		int mid = n%2==0 ? n/2:n/2+1;       // 根据长度的奇偶性,得到中间值
		int end = n%2==0 ? mid:mid-1;       // 左边字符串的终点
		String l = s.substring(0,end);                        // 左半部分字符串
		StringBuffer r = new StringBuffer(s.substring(mid));  // 右半部分
		if(l.equals(r.reverse().toString())) {                // 翻转右半部分与左半部分对比
			return true;
		}
		return false;
	}
}

发表于 2021-09-19 23:29:13 回复(0)
while 1:
    try:
        s = input()
        flag = 0
        if s[1:] == s[1:][::-1]:
            flag =1
            print(s[1:][::-1])
        elif s[:-1] == s[:-1][::-1]:
            flag =1
            print(s[:-1][::-1])
        else:
            for i in range(1,len(s)-1):
                new = s[0:i]+s[i+1:]
                if new == new[::-1]:
                    print(new)
                    flag = 1
                    break
        if flag == 0:
            print("false")
    except:
        break
发表于 2021-09-10 22:04:58 回复(0)
如果原字符串本身回文,也要删除1个字符,回文字符串删除第length/2位置的字符后依然回文。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        char[] str = input.next().toCharArray();
        int left = 0, right = str.length-1, pos = -1;
        boolean flag = true, modify = false;
        while(left <= right) {
            if(str[left]==str[right]) {
                left++;
                right--;
            } else {
                if(!modify) {
                    modify = true;
                    if (str[right] == str[left + 1]) {
                        //删除左边的
                        pos = left;
                        left++;
                    } else if (str[left] == str[right - 1]) {
                        //删除右边的
                        pos = right;
                        right--;
                    } else {
                        flag = false;
                        break;
                    }
                } else {
                    flag = false;
                    break;
                }
            }
        }
        if(!modify) {
            pos = str.length/2;
        }
        if(flag) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < str.length;i++) {
                if(i!=pos) {
                    sb.append(str[i]);
                }
            }
            System.out.println(sb.toString());
        } else {
            System.out.println(false);
        }
    }
}


发表于 2021-06-29 15:02:01 回复(0)
s = input()  # 获得输入


def judge(s):
    for i in range(0, int(len(s) / 2)):  # 左右元素比较
        if s[i] == s[len(s) - 1 - i]:
            continue
        else:
            return 'false'
    return 'true'


def test(s):
    if len(s) == 0:  # 长度为0
        return 'false'
    for i in range(0, len(s)):
        str1 = s[:i] + s[i + 1:]  # 删除一位后得到str1
        if judge(str1) == 'true':  # str1 判断是否回文
            return str1
        else:
            continue
    return 'false'


print(test(s))
发表于 2021-06-17 19:43:42 回复(0)
#include<iostream>
#include<string>
using namespace std;

class Solution {
public:
	string validPalindrome(string str) {
		string s = str;
		int i = 0, j = s.size() - 1, erase_num = 0;		// i,j分别指向字符串头和尾
		while (i < j) {
			if (s[i] != s[j]) {
				erase_num++;		// 检测到字符不等,说明需要进行删除操作,操作数自加1
				break;				// 同时跳出while循环,进行下一步删除操作
			}
			i++;
			j--;
		}
		if (erase_num == 0) {
			str.erase(str.begin() + i);
		}
		if(erase_num== 1) {
			erase_num = 0;		// 重置删除操作次数
			int m = i + 1, n = j;
			// 将i指针向后移动一位
			while (m < n) {
				if (s[m] != s[n]) {
					erase_num++;		// 字符再次不相等,说明i指针向后移动1次,并不能使s成为回文串
					break;				// 跳出循环后,复原i,j指针
				}
				m++;
				n--;
			}
			if (!erase_num) {
				str.erase(str.begin() + i);
				return str;
			}
			m = i, n = j - 1;	// 将j指针向前移动一位
			while (m < n) {
				if (s[m] != s[n]) {
					erase_num++;
					break;	
				}
				m++;
				n--;
			}
			str.erase(str.begin() + j);
		}
		if(erase_num== 2) {
			// 删除一个字符并不能满足条件
			return "false";
		}
		return str;
	}
};

int main() {
	string s;
	cin >> s;
	Solution sol;
	string res = sol.validPalindrome(s);
	cout << res << endl;
}

发表于 2021-06-17 16:58:42 回复(0)
把最中间位置删掉就可以了
发表于 2021-06-17 15:44:50 回复(0)
线性复杂度
#include <iostream>
 
using namespace std;
 
int main() {
     
    string input;
    cin >> input;
    //思路从两头到中间,发现不同只能跳一次,看那边先跳如果两种跳法都不同就失败,成功相遇就成功
    int len = input.size();
    int i = 0, j = len - 1;
    int skipflag = 1;
    int skipidx = 0;
    while (i < j) {
        if (input[i] != input[j]) {
            if (skipflag) {
                if (input[i + 1] == input[j]) {
                    skipidx = i;
                    skipflag = 0;
                    i++;
                } else if (input[i] == input[j - 1]) {
                    skipidx = j;
                    skipflag = 0;
                    j--;
                } else {
                    cout << "false" << endl;
                    return 0;
                }
            } else {
                cout << "false" << endl;
                return 0;
            }
        } else {
            i++;
            j--;
        }
    }
    string output;
    for (int i = 0; i < skipidx; i++) {
        output += input[i];
    }
    for (int i = skipidx + 1; i < len; i++) {
        output += input[i];
    }
    cout << output << endl;
    return 0;
}


发表于 2021-06-16 23:08:50 回复(0)
s=input()
sl=[i fori ins]
#先删除 再判断是不是回文
#1. 删除第一个不一样的字符
r,l=0,len(s)-1
whiler!=l andsl[r]==sl[l]:
    r+=1
    l-=1
sl.remove(s[r+1])
s2=''.join(sl)#删除第一个不一样的字符后的字符串
sr=s2[::-1]#倒序输出
#2. 判断删除后的字符串是否为回文数
ifs2==sr:
    #是回文数,返回s2
    print(s2)
else:
    print('false')#不是,返回false

您的代码已保存
程序异常退出,请检查是否存在语法错误或者数组越界非法访问等情况
Traceback (most recent call last):
File "/tmp/a.py3", line 6, in <module>
while r!=l and sl[r]==sl[l]:
IndexError: list index out of range

求问怎么会出现这个错误,本地编译器可以编译,自测也可以,但提交运行就错了
编辑于 2021-06-16 21:58:31 回复(0)
直接利用reverse函数,哈哈哈哈哈哈
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string IsValid(string& str) {
    int index = -1;
    while (index < int(str.size())) {
        string NewStr = "";
        for (int i = 0; i < str.size(); i++) {
            if (i != index) {
                NewStr += str[i];
            }    
        }
        string NewStr2 = NewStr;
        reverse(NewStr.begin(), NewStr.end());
        if (NewStr == NewStr2) return NewStr2;
        index++;
    }
    return "false";
}

int main() {
    string str;
    cin >> str;
    cout << IsValid(str);
}
发表于 2021-06-16 21:57:26 回复(0)