蘑菇街2016研发工程师编程题--回文串

本文主要是介绍蘑菇街2016研发工程师编程题--回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个字符串，问是否能通过添加一个字母将其变为回文串。

输入描述:

一行一个由小写字母构成的字符串，字符串长度小于等于10。

输出描述:

输出答案(YES\NO).

示例1

输入
coco
输出
YES

解法1

使用动态规划，先看一下回文串的性质，如果一个字符串为回文串，那么翻转这个字符串以后跟原来的子串相同如下：
这里写图片描述
根据题目如果加一个字符就能使字符串成为回文串，那么原字符串和翻转后的字符串的最多只有一个位置字符不同，也就是说原字符串和翻转后的字符串的最长公共子序列+1>=原字串。如下

上图中绿色部分为最长公共子序列，此时只有一个字符不相同，只要在最右边增加一个c字符就构成了回文串，如下：
这里写图片描述
因此只要求出原字符串与其翻转后字符串的最长子序列如果最长子序列长度+1>=原字符串长度增加一个字符就一定能构成回文。

代码

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.next();palidrome(str);}sc.close();}public static void palidrome(String str){//将str进行翻转成str1String str1=new StringBuffer(str).reverse().toString();//使用动态规划求str1和str的最长子序列int [][]dp=new int[str.length()][str.length()];if(str.charAt(0)==str1.charAt(0))dp[0][0]=1;for(int i=1;i<str.length();i++){if(str.charAt(0)==str1.charAt(i))dp[0][i]=1;else dp[0][i]=dp[0][i-1];if(str1.charAt(0)==str.charAt(i))dp[i][0]=1;else dp[i][0]=dp[0][i-1];}for(int i=1;i<str.length();i++)for(int j=1;j<str.length();j++){if(str.charAt(i)==str1.charAt(j))dp[i][j]=dp[i-1][j-1]+1;else {dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);}}if(dp[str.length()-1][str.length()-1]>=str.length()-1)System.out.println("YES");else {System.out.println("NO");}}
}

关于最长子序列的动态规划可以参考我的这篇博客最长公共子序列

解法2

假如一个字符串为回文串，那么使用两个指针head 从前往后遍历字符串和 tail从后往前遍历字符串，那么head和tail指向的字符一定相同。
这里写图片描述
因此本方法的思路是使用两个指针分别从前往后和从后往前遍历，如果两个指针指向的字符相同，那么继续遍历下一个字符，如果两个指针指向的字符不同，有两种方法，可以考虑在head指针指向的地方处加一个字符也可以考虑在tail指针指向的地方处加一个字符，继续遍历，选择加字符最小的方式。使用计数器没增加一个字符加1，如果最后计数器的值大于等于2那么NO，否则YES。

public static void palidrome(String str){int count=palidrome(str, 0, str.length()-1);if(count>=2)System.out.println("NO");else {System.out.println("YES");}}public static int  palidrome(String str,int start,int end){int cout=0;if(start>=end){return 0;
//如果start指向的字符和end指向的字符不同，那么选择在头部加字符和尾部加字符最小代价。if(str.charAt(start)!=str.charAt(end)){//在尾部加字符，尾部指针不动，头部指针向后移。int left=palidrome(str, start+1, end);//在头部加字符，头部指针不动，尾部指针向前移。    int right=palidrome(str, start, end-1); cout=Math.min(left, right)+1;}else {//头部和尾部字符相同，两个指针往中间移cout=palidrome(str, start+1, end-1);}return cout;}