给定一个字符串，问是否能通过添加一个字母将其变为回文串。
[编程题]回文串
/***判断原字符串和翻转字符串的最长公共子序列长度是否比原字符串长度小1或相等*/importjava.util.*;publicclassMain{publicstaticintlcs(String s, String s1){if(s == null|| s1 == null) {return0;}intm = s.length();intn = s1.length();int[][] dp = newint[m + 1][n + 1];dp[0][0] = 0;for(inti = 1; i < m; i++) {dp[0][i] = 0;}for(inti = 1; i < m; i++) {dp[i][0] = 0;}for(inti = 1;i < m + 1; i++) {for(intj = 1; j < n + 1; j++) {if(s.charAt(i - 1) == s1.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else{dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}returndp[m][n];}publicstaticvoidmain(String[] args) {Scanner scanner = newScanner(System.in);while(scanner.hasNext()) {String s= scanner.nextLine();String s1 = newStringBuilder(s).reverse().toString();intlen = lcs(s, s1);if(s.length() - len <= 1) {System.out.println("YES");} else{System.out.println("NO");}}}}
发表于 2015-09-22 15:38:21
回复(7)
//时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String as[]){
Scanner in=new Scanner(System.in);
while(in.hasNext()){
String s=in.next();
System.out.println(getAns(s.toCharArray(),0,s.length()-1,false)?"YES":"NO");
}
}
private static boolean getAns(char[] a,int start,int end,boolean flag){
if(end<=start){
return true;
}
if(a[start]==a[end]){
return getAns(a,start+1,end-1,flag);
}
else{
if(flag){
return false;
}
return getAns(a,start,end-1,true)||getAns(a,start+1,end,true);
}
}
}
编辑于 2016-08-28 14:48:14
回复(5)
最简单的思路：从结果来考虑，如果长度为n的字符串添加一个字符能成为回文串，那么删除一个字符也能成为回文，因为这个两个字符是对称的位置。如果删除的是中间位置字符的话，那么原字符串本身必为回文；如果删除的是两端字符的话，那么长度为n-1的两个子串必有一个也是回文。
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
if (isPa(s.substring(0, s.length() - 1)) || isPa(s.substring(1, s.length()))
|| isPa(s)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
public static boolean isPa(String s) {
return new StringBuilder(s).reverse().toString().equals(s);
}
}
编辑于 2016-08-10 20:39:23
回复(4)
发现点赞较多的居然是n平方的复杂度，不能忍。
O(n)就行啦，双指针，一前一后。遍历一次就可以了。
import java.util.Scanner;
/**
* Created by lzq on 17-7-2.
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str = in.next();
int flag = 0;
int i = 0, j = str.length() - 1;
while (i <= j) {
if (str.charAt(i) != str.charAt(j)) {
if (i + 1 <= j && str.charAt(i + 1) == str.charAt(j)) {
i++;
flag++;
} else if (j - 1 >= i && str.charAt(i) == str.charAt(j - 1)) {
j--;
flag++;
} else {
flag+=2;
break;
}
} else {
i++;
j--;
}
}
if (flag < 2) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
编辑于 2017-07-04 10:43:02
回复(1)
O（n）的复杂度遍历比较，头和尾往中间靠拢，即可#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
char str[12];
while(~scanf("%s",str)){
size_t len = strlen(str);
int head = 0;
int end = len-1;
bool space = true;
len = len/2;
while(head<end){
if(str[head] != str[end]){
if(!space){
break;
}
space = false;
if(str[head+1] == str[end]){
head++;
}else{
end--;
}
}else{
end--;
head++;
}
}
puts(head >= end ? "YES":"NO");
}
}
发表于 2016-08-28 10:31:22
回复(0)
//找到第一个前后不匹配的位置，然后检查之间的子串分别连接两端不匹配字符构成的两个串是否是回文串
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;
bool IsHuiWen(string str)
{
for(int i = 0; i<str.size()/2;i++)
{
if(str[i] != str[str.size()-1-i])return false;
}
return true;
}
int main()
{
string str;
while(cin>>str)
{
int flag = false;
int i;
for(i = 0; i<str.size()/2;i++)
{
if(str[i] != str[str.size()-1-i])break;;
}
if(i == str.size()/2)flag = true;
else flag = (IsHuiWen(str[str.size()-1-i]+str.substr(i,str.size()-2*i)) || IsHuiWen(str.substr(i,str.size()-2*i)+str[i]));
if(flag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
};
return 0;
}
发表于 2016-08-17 23:22:04
回复(2)
错误思路！！！（测试用例不完全，竟然可以AC）
感觉你们的都好复杂啊！如果可以添加一个字母成为回文串，那么原字符串或者除去头部的字符串或者除去尾部的字符串一定是回文串！
#include <iostream>
#include <algorithm>
using namespace std;
bool isPa(const string& s){
string r = s;
reverse(r.begin(), r.end());
return r == s;
}
int main(){
string str;
while(cin>>str){
string str_0(str.begin()+1, str.end());
string str_1(str.begin(), str.end()-1);
string ans = "YES";
if(str != "" && !isPa(str) && !isPa(str_0) && !isPa(str_1)){
ans = "NO";
}
cout << ans << endl;
}
return 0;
}
编辑于 2016-03-31 16:39:38
回复(5)
时间复杂度O(n)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
String s = scan.nextLine();
char[] c = s.toCharArray();
int i = 0, j = c.length - 1;
boolean result = true;
while (i < j) {
// i从左向右扫描，j从右向左扫描，找到第一对不相同的字符c[i]和c[j]
if (c[i] != c[j]) {
// 此时c[i]~c[j]不是回文串
// 只有当c[i+1]~c[j]为回文串或c[i]~c[j-1]为回文串时
// 才能通过添加一个字符使c[i]~c[j]成为回文串
// （若c[i+1]~c[j]为回文串，就在c[j]的右边添加和c[i]相同的，
// 若c[i]~c[j-1]为回文串，就在c[i]的左边添加和c[j]相同的）
result = isHuiWen(c, i + 1, j) || isHuiWen(c, i, j - 1);
break;
}
i++;
j--;
}
System.out.println(result? "YES" : "NO");
}
}
private static boolean isHuiWen(char[] c, int l, int r) {
int i = l, j = r;
while (i < j) {
if (c[i++] != c[j--]) {
return false;
}
}
return true;
}
}
发表于 2018-03-06 20:12:18
回复(0)
思路一：暴力，超级暴力。。。O(n2),因为题目说了字符串的长度不会超过10，也没想起其他方法，所以直接暴力写了一下。。。
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
bool isPlalindrome(string s){
string s1=s;
reverse(s1.begin(),s1.end());
if(s1==s)
return true;
else
return false;
}
int main(){
string s;
while(cin>>s){
map<char,int> tab;
bool flag=0;
for(int i=0;i<s.size();i++){
if(tab[s[i]]==0){
tab[s[i]]++;
string s1=s;
string::iterator itr=s1.begin();
for(;itr<=s1.end();++itr){
s1.insert(itr,1,s[i]);
if(isPlalindrome(s1)){
cout<<"YES"<<endl;
flag=1;
break;
}
s1=s;
}
}
if(flag==1)
break;
}
if(flag==0)
cout<<"NO"<<endl;
}
}
思路二：添加一个字符成为回文串相当于删掉一个字符是回文串，双指针从两边扫描，遇到不相等的，有两种选择，删掉前面的和删掉后面的，所以遍历两遍。用O(n)的复杂度就可以解决
#include<iostream>
#include<string>
using namespace std;
bool isPlalindrome(string s){
int i=0,j=s.size()-1;
while(i<=j&&s[i]==s[j]){
i++;
j--;
}
if(i>j)
return true;
else
return false;
}
int main(){
string s;
while(cin>>s){
int i=0,j=s.size()-1;
int cnt1=0,cnt2=0;
while(i<=j){
if(s[i]!=s[j]){
i++;
cnt1++;
}
else{
i++;
j--;
}
}
i=0,j=s.size()-1;
while(i<=j){
if(s[i]!=s[j]){
j--;
cnt2++;
}
else{
i++;
j--;
}
}
if(cnt1==1||cnt2==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
发表于 2017-06-26 16:15:43
回复(1)
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int main(){
string str,str1;
while(cin >> str){
int i,j,l = str.length();
for(i=0;i<=l;i++){
str1 = str;
for(j=l;j>i;j--)
str1[j] = str[j-1];
if(l%2 == 0 && i == l/2)
str1[i] = 'x';
else if(i<l/2)
str1[i] = str[l-i-1];
else
str1[i] = str[l-i];
for(j=0;j<l/2;j++){
if(str1[j] != str1[l-j])
break;
}
if(j == l/2){
cout <<"YES"<<endl;
break;
}
}
if(i == l+1)
cout<<"NO"<<endl;
}
}
//更新更简单方法，增加一个是回文，那删除一个也是回文。具体删除方式可以采取模拟的方式，头尾遍历，i，j各指向头尾，如果相同则i++。j--。如果不同则说明出现不同，需要删除某个数故x--。
然后看str[i+1]是否等于str[j]，则删除第i个;或者看str[i]是否等于str[j-1]，则删除第j个;如若都不成立，则说明两个都得删除。
当删除个数大于等于2时，跳出循环。说明要构成回文需要删除两个以上字符故NO；
删除个数小于等于1时，则说明不删除或者删除一个就能构成回文，即添加一个也能构成回文，故YES！附上AC代码
#include<iostream>
#include<string>
using namespace std;
int main(){
string str;
while( cin >> str ){
int i,l = str.length(),x = 2,j = l - 1;
for(i=0;i<j;i++,j--){
if(str[i] != str[j]){
x--;
if(str[i+1] == str[j])
i++;
else if(str[i] == str[j-1])
j--;
else
x--;
}
}
if(x>0)
cout << "YES" <<endl;
else
cout << "NO" <<endl;
}
}
编辑于 2017-06-22 12:16:27
回复(0)
#include <string>
#include <iostream>
using namespace std;
// 添加一个可以构成回文串，则删除一个必定可以构成回文串存在漏洞
// 例如：aabb,添加一个字符明显可以构成回文串，但删除一个后构不成回文串
// 因此，可以选择先对源字符串进行判断，若其不是回文串，在进行删除判断。。。
bool isPalindrome(string& str, int start, int end)
{
for(int i = start, j = end; i <= (end - start)/2; i++, j--)
{
if(str[i] != str[j]) return false;
}
return true;
}
void copyExpectOne(string& str, int exIndex, string& ret)
{
for(int i = 0; i < str.size(); i++)
{
if(i != exIndex) ret += str[i];
}
}
int main()
{
string str;
while(cin >> str)
{
bool flag = true;
if(isPalindrome(str, 0, str.size() - 1))
{
cout << "YES" << endl;
continue;
}
for(int i = 0; i < str.size(); i++)
{
string tmp;
copyExpectOne(str, i, tmp);
if(isPalindrome(tmp, 0, tmp.size() - 1))
{
cout << "YES" << endl;
flag = false;
break;
}
}
if(flag)
cout << "NO" << endl;
}
return 0;
}
发表于 2017-03-14 16:34:24
回复(2)
说我输出结果为空，可我用vs和dev自测都是没有问题的，有看到的同学帮忙测一下，看看是否是机器原因#include <iostream>
#include <string>
using namespace std;
bool juage(string a, int b)
{
for(int i = 0; i <= b/2; i++){
if(a[i] == a[b-1-i])
continue;
else
return false;
}
return true;
}
int main()
{
string s1, s2;
cin >> s1;
int size = s1.size(), flag = 0;
if(size == 1){
cout << "NO";
return 0;
}
for(int i = 0; i < size; ++i){
s2 = s1;
s2.erase(s2.begin()+i);
if(juage(s2, size-1)){
cout << "YES";
return 0;
}
}
cout << "NO";
return 0;
}
发表于 2019-04-07 15:17:42
回复(0)
从两端开始搜索，碰到不相同的，将剩余部分分别去掉头部和尾部的一个字符，若可以是回文串，则YES；若字符串本身就是回文串，则YES
def check(s):
"""检查一个字符串是否为回文串"""
for i in range(len(s)):
j = len(s) - 1 - i
if i == j:
break
if s[i] != s[j]:
return False
return True
while True:
try:
s = input()
except EOFError:
break
for i in range(len(s)):
j = len(s) - 1 - i
if i == j:
print('YES')
break
if s[i] != s[j]:
if check(s[i:j]) or check(s[i+1:j+1]):
print('YES')
break
else:
print('NO')
break 运行时间：23ms
占用内存：3448k
编辑于 2018-08-30 15:16:31
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.nextLine();
Main.addLeastChar(str);
}
}
/*
* 核心思想是：组装出str与其翻转的字符strMirror的最长公共子序列，举例：
* str="abceba",strMirror="abecba"，最长公共子序列为
* "abcba"为5，str的长度为6，只要满足str的长度-最长公共子序列<=1(添加一个字符，满足题意)，即可输出YES，反之则输出NO
*/
/*
* 其他位置为三种情况：1.可能是dp[i - 1][j],i.e:str1:"A1BC2"，str2："AB34C" str1[0..3](A1BC
* )与str2[0...4](AB34C)的最长公共子序列为"ABC",即dp[3][4]=3而dp[4][4
* ]也是3,具体可同dp[3][4]一样分析
* //2.也可能是可能是dp[i][j-1]，i.e:str1:"A1BC2"，str2："AB3C4"，str1[0..4](A1BC2 // *
* )与str2[0...3](AB3C)的最长公共子序列为"ABC",dp[4][3]，而dp[4][4]也是3
* 3.str1[i]==str2[j] 还可能是dp[i-1][j-1]+1,i.e:str1:"ABCD"，str2："ABCD"
*/
public static void addLeastChar(String str) {
String str1 = str;
String str2 = new StringBuilder(str).reverse().toString();
int[][] dp = getdp(str1, str2);
int len = str1.length();
int lisLen = dp[str1.length() - 1][str2.length() - 1];
boolean res = len - lisLen <= 1;
if (res)
System.out.println("YES");
else
System.out.println("NO");
}
// dp[i][j]是str1[0...i]和str2[0...j]的最长公共子序列的长度
public static int[][] getdp(String str1, String str2) {
char[] chas1 = str1.toCharArray();
char[] chas2 = str2.toCharArray();
int[][] dp = new int[chas1.length][chas2.length];
dp[0][0] = chas1[0] == chas2[0] ? 1 : 0;
for (int i = 1; i < chas1.length; i++) {// 组装第一列
dp[i][0] = Math.max(dp[i - 1][0], chas1[i] == chas2[0] ? 1 : 0);
}
for (int j = 1; j < chas2.length; j++) {// 组装第一行
dp[0][j] = Math.max(dp[0][j - 1], chas1[0] == chas2[j] ? 1 : 0);
}
for (int i = 1; i < chas1.length; i++) {// 组装其他元素
for (int j = 1; j < chas2.length; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (chas1[i] == chas2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp;
}
}
编辑于 2018-03-12 21:14:48
回复(0)
我的思路，还有其他几种思路。不过越想越骚啊。
package com.special.first;
import java.util.Arrays;
import java.util.Scanner;
/**
* 蘑菇街05-回文串
* 判断是否可以添加一个字符形成回文串
*
* 我的思路可能不是最优的，但是思路简单
* 首先我们知道一个n个长度的字符串，他有n + 1个位置可以插入
* 所以我们就这样模拟插入的过程，插入时，该位置之后的字符要右移（注意最后一个位置不用右移）
* 移动后，空出来的temp[i]值应该等于temp[n + 1 - 1 - i](简写为temp[n - i])
* 然后判断此时是否是回文串即可
*
* 为什么要temp[i]=temp[n - i]？
* 因为我们的目的是构成回文串，只有对称的值相等，才能构成，所以必须使temp[i]=temp[n - i]
*
* 优化：因为如果外围不管的左边插入还是右边插入都构不成字符串的话，就可以直接结束了
* 外围都确保不了对称，即使里面对称又有何用？
* 这里只需遍历一半即可，然后处理i，n - i的插入，你可以尝试一下，有时间我也尝试一下
* Create by Special on 2018/3/1 11:40
*/
public class Pro028 {
public static boolean isPlalinDrome(char[] chars){
for(int i = 0, j = chars.length - 1; i < j; i++, j--){
if(chars[i] != chars[j]){
return false;
}
}
return true;
}
public static String isOk(char[] chars, int n){
boolean isPlalinDrome = false;
char[] temp;
for (int i = 0; i <= n; i++) {
temp = Arrays.copyOf(chars, n + 1);
if(i < n) {
System.arraycopy(temp, i, temp, i + 1, n - i);
}
temp[i] = temp[n - i];
if(isPlalinDrome(temp)){
isPlalinDrome = true;
break;
}
}
return isPlalinDrome ? "YES" : "NO";
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
String str = input.nextLine();
char[] chars = str.toCharArray();
System.out.println(isOk(chars, str.length()));
}
}
}
发表于 2018-03-01 15:12:15
回复(0)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool check(string str)
{
string temp=str;
reverse(temp.begin(),temp.end());
return str==temp;
}
int main()
{
string input;
while(cin>>input)
{
if(check(input)||check(input.substr(1,input.size()))||check(input.substr(0,input.size()-1)))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
发表于 2018-02-10 11:35:32
回复(1)
#include <bits/stdc++.h>
using namespace std;
bool solve(string s,int start,int end,bool flag)
{ if(start>=end) return true; if(s[start]==s[end]) return solve(s,start+1,end-1,flag); else{ if(flag) return false; return solve(s,start,end-1,true) || solve(s,start+1,end,true); } }
int main()
{ string s; while(cin>>s) { int n = s.length(); cout<<(solve(s,0,n-1,false)?"YES":"NO")<<endl; } return 0;
}
发表于 2017-11-17 01:08:42
回复(0)
从两边同时向中间遍历，遇到不一样的字符只有两种操作：
1.在左边字符的左边添加一个字符
2.在右边字符的右边添加一个字符
如果添加后为回文，那么则可以，否则不可以。时间复杂度最好为O(n)，最差为O(n^2)
#include<iostream>
#include<string>
using namespace std;
bool isPar(string s){
bool res = true;
for(int i = 0; i < s.length()/2 + 1; i++){
if(s[i] != s[s.length()-i-1]) res = false;
}
return res;
}
int main(){
string a;
while(cin >> a){
int l = 0;
int r = a.length()-1;
while(l < r){
if(a[l] == a[r]){
l++;
r--;
}else{
a.insert(l,&a[r]);
if(isPar(a)){
cout << "YES" << endl;
}else{
a.erase(l,1);
if(r+1 >= a.length()) a = a+ a[l];
else a.insert(r+1,&a[l]);
if(isPar(a)){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
break;
}
}
}
return 0;
}
发表于 2017-11-06 18:54:49
回复(0)
看到上面好像还没有我这种思路：
- 首先写出任意一组回文序列，可以分奇数个元素或是偶数个元素（为了严谨故而区分讨论，其实最终处理方法一样），手动划去任意一个，观察可以得出剩余的元素中(设原来元素个数为aSize),可以组成(aSize/2-1)组能够相互配对的序列。
- 反向考虑，题设要求是“插入任意位置一个字母可以组成回文序列”，现在可以遍历从首位之前一位插入一个任意数字（不插入字母是避免冲突），目的是为了占位，然后按照回文数的判断方法进行判断即可。
需要注意的是在遍历每一个位置之前需要重新将计数器置零，以及注意stl中的insert（int pos,int num）指的是插入pos的前一位，因此为了将占位符插到这个string的最后，在循环的时候要取到string s.size()，而非string s.size()-1.
另外需要注意的是，在每次插入占位符后，判断完毕要将该处的占位符删掉。
#include<iostream>
#include<string>
using namespace std;
string a;
int cnt;
bool isPalindrome(int pos) {
a.insert(pos, "1");
int aSize = a.size();
for (int i = 0; i < aSize/2; i++) {
int b = aSize - i - 1;
if (a[i] == a[b]) {
cnt++;
}
}
a.erase(pos,1);
if (cnt == aSize / 2 - 1)
return true;
else
return false;
}
int main() {
freopen("Text.txt", "r", stdin);
while (cin>>a) {
int flag = 0;
int aSize = a.size();
for (int j = 0; j <= aSize; j++) {
cnt = 0;
if (isPalindrome(j) == true) {
flag = 1;
break;
}
}
if(flag == 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
发表于 2017-08-22 14:39:40
回复(0)
借鉴之前的回答中所说的：既然能通过增加一个字符变成回文串，那一定也可以通过删除一个字符变成回文串。
夕一啊 提供的理由是：如果一个回文串长度是偶数，那么说明都是成对出现的，待处理字符串增加一个和删除一个等价。如果一个回文串长度是奇数，那么说明要不增加的是中间那个单独的，删除时也是它，要么是成对出现的那些就和偶数情况一样了
已 AC：
#include <iostream>
#include <algorithm>
using namespace std;
bool isPa(string str) {
string tmp = str;
reverse(str.begin(), str.end());
return tmp == str;
}
int main() {
string str;
while (cin >> str) {
string ans = "YES";
if (!isPa(str)) {
ans = "NO";
for (int i = 0; i < str.size(); i++){
string tmp = str;
tmp.erase(i, 1);
if (isPa(tmp)) {ans = "YES"; break;}
}
}
cout << ans << endl;
}
return 0;
}
编辑于 2017-07-23 13:05:19
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-14 16:58:57 -
2022-09-11 10:47:49
-
2022-09-09 17:22:56
-
2022-09-05 16:39:39 -
2022-09-05 10:27:26
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
