5.最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2:

输入: "cbbd"
输出: "bb"

思路

1.可以使用中心扩展法来寻找此题的答案，而一个字符串的中心应该是2n-1个而不是n个，因为两个字母相同的话，该中心在其二者的“夹缝”中。
2.为了分割中心方便，我们可以将每个字母使用特殊符号分割，然后遍历整个字符串，最终寻找到最长子串。

Java代码实现

     public static String longestPalindrome(String s) {
        String str = "#";
        for (int i = 0; i < s.length(); i++) {
            str += s.charAt(i)+"#";
        }

        String longestStr = "";

        for (int i = 1; i < str.length(); i++) {
            String cur = longestPalindrome(str,i);
            if(longestStr.length()<cur.length())
                longestStr = cur;
        }
        return longestStr.replace("#","");
    }

    private static String longestPalindrome(String s,int index) {
        int left = index-1;
        int right = index+1;

        while(left>=0 && right<s.length()){
            if(s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }else {
                break;
            }
        }
        return s.substring(left+1,right);
    }