最长回文子串

思路：这个思路其实就是中心开花，我们循环遍历每一个节点，以这个节点为回文子串的最中间节点，然后对该节点调用一个寻求子串长度的方法：比较中心节点两边的节点是否相等，相等则继续向两边扩展，直到不相等 或者某一端到头。

例如字符串：acabacb  我们假设现在遍历到第四个节点b，对他调用寻求回文子串长度的方法，就会对比 3 5位置的元素是否相等 如果相等则aba是一个回文串 然后i-2 和i+2位置继续判断 最后得到回文子字符串长度返回 ，在主循环中添加两个变量start end 用来标记最长子串的长度 如果新获取的值更大 则更新。

其实我们忽略了 一种情况：最坏情况有两种 ：1最长子回文串长度为一 中心节点两端不相同

2最长回文子串长度为2 中心节点由两个相同的节点组成：例如acabbacb 中心节点是ab；

所以对于两种情况均调用寻求子串长度的方法，保留返回值较大值

public class Solution {

    public  String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "字符串非法";
        }
        int start = 0, end = 0;
        int len1=0, len2=0,len=0;
        for (int i = 0; i < s.length(); i++) {
            len1=expandAroundCenter(s,i,i);//最坏情况 单个节点是最长子串
            len2=expandAroundCenter(s,i,i+1);//最坏情况 两个相同的字符是最长子串
            len=Math.max(len1,len2);
            if(len>end-start){//字符串长度为 5 6 i都是3开始 end start坐标处理不一样
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start,end+1);//subString含头不含尾
    }

    public int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;//向两边扩展
            R++;
        }
        //因为循环的原因 现在的LR是最后一次跳出循环时的值
        return R-L-1;
    }
}

测试类

public class Test {
    public static void main(String[] args) {
        String s1 = "acabbacb";
        String sub1 = new Solution().longestPalindrome(s1);
        System.out.println(sub1);
    }
}

上面是题解思路，其实还有一种思路：学习动态规划的时候我们应该做过求两个字符串最长公共子序列长度的题，

我们如果把一个字符串反转（reverse）一下，然后把反转后的字符串和反转前的字符串求最长公共子序列，我们会发现得到的公共子序列其实就是最长回文子串。