蘑菇街2016招聘笔试（回文串）

题目

题目描述：给定一个字符串，问是否能通过添加一个字母将其变为回文串。
输入描述：一行一个由小写字母构成的字符串，字符串长度小于等于10。
输出描述：输出答案(YES\NO)。
输入例子：coco。
输出例子：YES。

分析

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

在本题中，最核心的部分就是判断字符串添加字母后是否为回文串，因此本文中的代码只针对这一功能编写。
初看此题，我们很容易想到去遍历实现，但未免太过繁杂。不妨思考一种更简单的方法：
添加一个字母之后变为回文串，即我们在从首尾端判断回文串的时候，容许一次错误，之后截取产生错误位置的两条不对等子串，判断子串是否为回文串即可。
以字符串“zcocoz”为例，第一个字符“z”和最后一个字符“z”相等，但是第二个字符和倒数第二个并不相等，因此，我们截取两条子串：从第二个字符到倒数第三个字符"coc"（相当于在字符串中第一、二位插入了一个“o”）,从第三个字符到倒数第二个字符“oco”（相当于在字符串倒数第二位和倒数第一位插入了一个“c”）,判断这两个字符串是否为回文串，其中有一个为回文串，即满足题意。

代码实现

public class Plalindrome {

    public static void main(String[] args) {
        long startMili=System.currentTimeMillis();// 当前时间对应的毫秒数
        System.out.println(isAddPlalindrome("acc"));
        System.out.println(isAddPlalindrome("sos"));
        System.out.println(isAddPlalindrome("ititewewtiti"));
        System.out.println(isAddPlalindrome("ititxystiti"));
        long stopMili=System.currentTimeMillis();// 当前时间对应的毫秒数
        System.out.println("程序运行共计："+(stopMili-startMili)+"毫秒");
    }
    
    public static boolean isAddPlalindrome(String text){
        for(int i=0;i<=text.length()/2;i++){
            if(!text.substring(i, i+1).equals(text.substring(text.length()-1-i, text.length()-i))){
                if(isPlalindrome(text.substring(i,text.length()-1-i))||isPlalindrome(text.substring(i+1,text.length()-i))){
                    return true;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    
    public static boolean isPlalindrome(String textString){
        for(int i=0;i<=textString.length()/2;i++){
            if(!textString.substring(i, i+1).equals(textString.substring(textString.length()-1-i, textString.length()-i))){
                return false;
            }
        }
        return true;
    }
}

运行结果

true
true
true
false
程序运行共计：1毫秒

本人博客

http://www.2maestro.me
会在网站中更新一些算法、电脑技巧等相关文字，目前还在初步建设阶段。