最长回文子串

题述

求一个子串的最长回文子串是常见算法题，所谓的回文子串就是正着读和反着读是一样的，其leetcode地址如下：
https://leetcode.com/problems/longest-palindromic-substring/

思路一

根据题述，我首先想到了穷举法，即找出字符串的所有子串，并验证其是否是回文子串来找到最长回文子串:

public String longestPalindromeIII(String s){
        if (s.length() == 0 || s.length() == 1) {
            return s;
        }
        int longestStr = 0;
        int longStart = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                int start = j;
                int end = i;
                while (start <= end){
                    if (s.charAt(start) == s.charAt(end)) {
                        start++;
                        end--;
                    }else {
                        break;
                    }
                }
                if (start > end) {
                    if (i - j + 1 > longestStr) {
                        longestStr = i - j + 1;
                        longStart = j;
                    }
                }
            }
        }
        return s.substring(longStart, longestStr +longStart);
    }

穷举法在思路上最好理解，实现起来很简单，但是其时间复杂度达到了n^3，其空间复杂度为o(1)

思路二

分析回文子串的性质发现，所有的回文子串都是中心对称的，也就是说我们可以移动对称中心来实现遍历和检验，每一次移动中心后都从中心处开始向两边检验对称性，考虑到如果回文子串长度为偶数，则实际的对称中心是不存在子串中的，所以需要构造一个奇数的回文子串，这里采用了向每一个子串中间添加‘#’来处理

public String longestPalindrome(String s) {
        if (s.length() == 0) {
            return "";
        }
        int start = 0;//最大回文子串开始下标
        int end = 0;//最大回文子串结束下标
        int max = 0;//最大回文子串总长度
        //预处理子串，向其中添加‘#’
        String handleStr = preHandleStr(s);
        //i为回文中心点
        for (int i = 0; i < handleStr.length(); i++) {
            int step = 1;//step为回文中心单边长度
            while (i - step >= 0 && i + step < handleStr.length()){
                if (handleStr.charAt(i - step) == handleStr.charAt(i + step)) {
                    if (step * 2 + 1 > max) {
                        max = step * 2 + 1;
                        start = i - step;
                        end = i + step;
                    }
                    step++;
                }else {
                   //这里主要是保证回文子串的最左和最右字符不能是我添加的‘#’，比如c#a#a，当回文中心为2或者3时其step都为2
                    if (handleStr.charAt(start) == '#') {
                        start++;
                        end--;
                        max-=2;
                    }

                   break;
                }
            }
        }
        return handleStr.substring(start, end + 1).replaceAll("#","");
    }

    private String preHandleStr(String s){
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder handleStr = new StringBuilder();
        handleStr.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            handleStr.append("#").append(s.charAt(i));
        }
        return handleStr.toString();
    }

思路三

该思路主要是优化思路二，在思路二中，会存在这样一种情况，比如：
cabadabae以第四位的d为中心位置时，发现其最长回文的右边界为第7位，此时以第2位为中心的回文子串长度和以第6位为中心的回文子串长度都是3，以第3位为中心的回文子串长度和以第5位为中心的回文子串长度都是1，但是以第7位为中心的回文子串长度并不一定和以第1位为中心的回文子串长度相等，因为第8为数据是未知的。也就是说，只要当前回文中心坐标与当前对称可参照的回文长度和小于已知的最右边界，则可以不用计算本次回文中心对应的回文长度

代码实现

private String preHandleStr(String s){
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder handleStr = new StringBuilder();
        handleStr.append('#');
        for (int i = 0; i < s.length(); i++) {
            handleStr.append(s.charAt(i)).append("#");
        }
        return handleStr.toString();
    }

    /**
     *
     */
    public String longestPalindromeII(String s){
        // 先预处理字符串
        String str = preHandleStr(s);
        // 处理后的字串长度
        int len = str.length();
        // 右边界
        int rightSide = 0;
        // 右边界对应的回文串中心
        int rightSideCenter = 0;
        // 保存以每个字符为中心的回文长度一半（向下取整）
        int[] halfLenArr = new int[len];
        // 记录回文中心
        int center = 0;
        // 记录最长回文长度
        int longestHalf = 0;
        for(int i = 0; i < len; i++) {
            // 是否需要中心扩展
            boolean needCalc = true;
            // 如果在右边界的覆盖之内
            if(rightSide > i) {
                // 计算相对rightSideCenter的对称位置
                int leftCenter = 2 * rightSideCenter - i;
                // 根据回文性质得到的结论
                halfLenArr[i] = halfLenArr[leftCenter];
                // 如果超过了右边界，进行调整
                if(i + halfLenArr[i] > rightSide) {
                    halfLenArr[i] = rightSide - i;
                }
                // 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
                if(i + halfLenArr[leftCenter] < rightSide) {
                    // 直接推出结论
                    needCalc = false;
                }
            }
            // 中心扩展
            if(needCalc) {
                while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
                    if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
                        halfLenArr[i]++;
                    } else {
                        break;
                    }
                }
                // 更新右边界及中心
                rightSide = i + halfLenArr[i];
                rightSideCenter = i;
                // 记录最长回文串
                if(halfLenArr[i] > longestHalf) {
                    center = i;
                    longestHalf = halfLenArr[i];
                }
            }
        }
        // 去掉之前添加的#
        StringBuffer sb = new StringBuffer();
        for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }