最长回文字符串-Java实现_最短回文字符串java

一、问题描述

回文字符串定义：如果一个字符串正着读和反着读是一样的，那它就是回文串例如：aba 、 abcba 。
要求：
给出一个字符串：asdsaasa
返回一个最长的回文字符串：asdsa

二、解法（回文字符串为奇数）

public class Test {
    public static void main(String[] args) {
        String str = "sgfsasaopoiuydfghgfdtrewqirgabnirweir";
        System.out.println("答案是："+searchMaxOddStr(str));
    }

    /**
     * 查询最长回文字符串。@author YYM
     * 只能查询到如"asdsa"类型的字符串（总长度为奇数）。
     * 而无法查询"asddsa"类型的（总长度为偶数）。
     * 若要查询asdsa类型的，请对原字符串数据进行处理。
     * @param str 待分析的字符串
     * @return 结果字符串
     */
    public static String searchMaxOddStr(String str) {
        if (str.equals("")) {
            return "";
        }
        String answer;//答案字符串
        int maxLen = 0;//存放当前回文字符串的"半径".
        int maxCenter = 0;//存放当前回文字符串的中心。
        int nowCenter=0;
        int nowLen =0;
        boolean flag = true;
        char[] list = str.toCharArray();
        for(nowCenter = 0;nowCenter< list.length;) {
            while(flag) {//开始执行一个中心点的判断
                if((nowCenter-nowLen)>=0 && nowCenter+nowLen<list.length) {//防止越界
                    if(list[nowCenter-nowLen]==list[nowCenter+nowLen]) {
                        if(maxLen<nowLen) {
                            maxLen = nowLen;
                            maxCenter = nowCenter;
                        }
                        nowLen++;
                    }else flag=false;
                }else flag =false;
            }
            nowCenter++;//判断下一个
            flag = true;//恢复初始状态
            nowLen=1;//恢复初始长度
        }
        answer = str.substring(maxCenter-maxLen,maxCenter+maxLen+1);//截取
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

算法分析：由于是挨个遍历每个字符，然后往两边扩展比较，所以时间复杂度为O(n^2)..

三、如果最长回文是偶数呢？

简单，解决办法是把字符串每一个字符之间添加一个不可能出现在字符串中的符号，再传入方法里：
如：asddsaasasa
改成：#a#s#d#d#s#a#a#s#a#s#a#
再传入上面写的方法，得到返回字符串后再去掉“#”即可。