回文串

import java.util.*;


public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String s2 = sc.next();
        solution(s);
        solution(s2);

    }

    private static void solution(String s) {
        LinkedHashSet<Character> set = new LinkedHashSet<>();
        HashMap<String, String> map = new LinkedHashMap<>();
        for(int i=0;i<s.length();i++){
           set.add(s.charAt(i));
        }
        StringBuilder stringBuilder = new StringBuilder(s);
        Iterator<Character> iterator = set.iterator();
        while (iterator.hasNext()){
            Character c = iterator.next();
            for(int i=0;i<=s.length();i++){
                String s1 = stringBuilder.insert(i, c).toString();
                if(!map.containsKey(s1)){
                    String s2 = findroundString2(s1);
                    map.put(s1,s2);
                }
                stringBuilder.delete(0,stringBuilder.length());
                stringBuilder.append(s);
            }
        }
        String RESULT="NO";
        Set<Map.Entry<String, String>> entries = map.entrySet();
        Iterator<Map.Entry<String, String>> iterator1 = entries.iterator();
        while (iterator1.hasNext()){
            Map.Entry<String, String> next = iterator1.next();
            String value = next.getValue();
            if(value=="YES"){
                RESULT=value;
                break;
            }
        }

        System.out.println(RESULT);
    }

    private static String findroundString2(String s) {
        String flag = "";
            StringBuilder builder = new StringBuilder(s);
            builder.reverse();
            StringBuilder builder1 = new StringBuilder(s);
            if(builder.toString().equals(builder1.toString())){
                flag="YES";
            }


        return flag!=null?flag:"NO";
    }

}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Set<String> set = new HashSet<>();
        while (in.hasNext()){
            String s = in.next();
            for (int i = 0; i <s.length() ; i++) {
                set.add(String.valueOf(s.charAt(i)));
            }
            List<String> list = new ArrayList<>(set);
            if(just(list,s)){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }

    private static boolean just(List<String> list, String s) {
        for (int j = 0; j < list.size(); j++) {
            for (int k = 0; k <= s.length() ; k++) {
                StringBuffer ** = new StringBuffer(s);
                StringBuffer str = **.insert(k,list.get(j));
                StringBuffer str1 = new StringBuffer(str).reverse();
                if(str.toString().equals(str1.toString())){
                    return true;
                }
            }
        }
        return false;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            StringBuilder sb = new StringBuilder(s);
            for (int i = 0; i < sb.length() - 1; i++) {
                for (int j = 0; j <= 26; j++) {
                    sb.insert(i, (char) ('a' + j));
                    String sb2 = String.valueOf(sb);
                    sb.reverse();
                    if (sb2.equals(String.valueOf(sb))) {
                        System.out.println("YES");
                        return;
                    } else {
                        sb.deleteCharAt(sb.length() - 1 - i);
                        sb.reverse();
                    }
                }
            }
            System.out.println("NO");
        }
    }
}
//这个编译器有毒,idea上通过了这上面的测试用例,自测也通过了卡住的测试用例,可是这就是报空

 import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.next();
            System.out.println(Helper(str));
        }
    }
    public static String Helper(String str){
        int len = str.length();
        int i = len/2;
        if(len%2 == 0){
            if((str.substring(0,i).contains(new StringBuffer(str.substring(i+1)).reverse().toString())) ||
                    str.substring(i).contains(new StringBuffer(str.substring(0,i-1)).reverse().toString())){
                return "YES";
            }
            return "NO";
        }else{
            if((str.substring(0,i+1).contains(new StringBuffer(str.substring(i+1)).reverse().toString())) ||
                    str.substring(i).contains(new StringBuffer(str.substring(0,i)).reverse().toString())){
                return "YES";
            }
            return "NO";
        }
    }
}

使用dp求解
public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            String s=scanner.next();
            boolean[][] dp=new boolean[s.length()][s.length()];
            for(int i=s.length()-1;i>=0;i--){
                for(int j=i;j<s.length();j++){
                    dp[i][j]=s.charAt(i)==s.charAt(j)&&(i>j-2||dp[i+1][j-1]);
                }
            }
            int j=s.length()-1;
            int i=0;
            while (i<j){
                if(s.charAt(i)!=s.charAt(j))break;
                i++;
                j--;
            }
            if(i==j||dp[i+1][j]||dp[i][j-1]) System.out.println("YES");
            else System.out.println("NO");
        }
    }

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;
    }

}

发现点赞较多的居然是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");
            }
        }
    }
}

/**
有个case: "jnwbbwnjb"本地可以通过，线上却通不过，也没有提示，
我使用暴力求解（逃。。。），各位大虾知道是怎么回事吗？
*/
public static boolean  addedStrIsPalindrome(String str) {
        for (int i = 0; i < str.length(); i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                StringBuilder sb = new StringBuilder(str);
                sb.insert(i, ch);
                if (isPalindrome(sb.toString())) {
                    return true;
                }
            }
        }
        return false;
    }

/*
1.做完后，发现有人说既然增加一个能成为回文，那么删除一个也能成为回文，思路不错
2.本例联系了StringBuilder，一定要注意，只要没有new StringBuilder，修改的就还是原对象
3.易错点：利用StringBuilder的插入，都是插在i元素之前。而本题最后一个元素是要插在
第一个元素的左边，而第一个是要插在最后一个元素的右边的。
*/
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();            
            String res = "NO";
            if(isHuiWen(new StringBuilder(s))){
                res="NO";
            }else{                
                for(int i=0;i<=s.length()/2;i++){
                    if(s.charAt(i)!=s.charAt(s.length()-1-i)){
						StringBuilder B = new StringBuilder(s).insert(i,s.charAt(s.length()-1-i));                    
                        StringBuilder C = new StringBuilder(s).insert(s.length()-i,s.charAt(i));
                        if(isHuiWen(B) | isHuiWen(C)){
                            res = "YES";
                            break;
                        }
                	}
                }                
            }
            System.out.println(res);
        }
    }
    public static boolean isHuiWen(StringBuilder sb){
        StringBuilder sb1 = new StringBuilder(sb);
        if(sb1.reverse().toString().equals(sb.toString())){
            return true;
        }
        return false;
    }
}

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String s = sc.next();
			boolean flag = false;
			for (int i = 0; i < s.length(); i ++ ) {
				String str = s.substring(0, i) + s.substring(i + 1);
				StringBuilder sb = new StringBuilder();
				sb.append("#");
				for (int j = 0; j < str.length(); j ++ )
					sb.append(str.charAt(j) + "#");
				int start = sb.length() / 2;
				int end = sb.length() / 2;
				String temp = sb.toString();
				while (start >= 0 && end <= sb.length() - 1 && temp.charAt(start) == temp.charAt(end)) {
					if(start == 0 && end == temp.length() - 1) flag = true;
					start -- ;
					end ++ ;
				}
			}
			if(flag)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
}

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String line = scan.nextLine();
            char[] cs = line.toCharArray();
            char[] rs = new char[cs.length];
            for (int i = 0, j = cs.length - 1; i < cs.length; ++i, --j) {
                rs[i] = cs[j];
            }
            int[][] dp = new int[cs.length + 1][cs.length + 1];
            for (int i = 1; i <= cs.length; ++i) {
                for (int j = 1; j <= rs.length; ++j) {
                    if (cs[i - 1] == rs[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]);
                    }
                }
            }
            int len = dp[cs.length][cs.length];
            if (cs.length - len <= 1) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        scan.close();
    }
    
}

import  java.util.Scanner;

public class Main{
    public static void main(String args[]){
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            String A=input.next();
            String B="";
            for(int i=A.length()-1;i>=0;i--){
                B+=A.charAt(i);
            }
            A+=A.charAt(0);
            B+=B.charAt(0);
            if(IsHuiwen(A)||IsHuiwen(B)){
                System.out.println("YES");
            }else{
            System.out.println("NO");
            }
        }
    }
    public static boolean IsHuiwen(String A){
        boolean count=false;
        for(int i=0;i<A.length();i++){
            if(A.charAt(i)==A.charAt(A.length()-1-i)){
                count=true;
            }else{
                count=false;
                break;
            }
        }
        return count;
    }
}
//用自己的思想证明是可以的