一、题目

　　1、审题：

　　　　

　　2、分析

　　　　求字符串最长的回文子串

 

二、解答

　　1、分析： 

　　　方法一：

　　　　依次遍历字符串的字符，同时将该字符作为中间字符，向左右延伸进行比较，选出最长回文子串，此时回文子串有奇数偶数之分，为了方便，可以在所给字符串相隔字符之间均加上字符“#", 从而化为只有奇数的一种情况，最终将所求出的最长回文子串的‘#’处理即可。

　　

class Solution {    public String longestPalindrome(String s) {        int len = s.length();        if(len == 1 || len == 0)            return s;        int maxLen = 1, start, end, median = 1;        StringBuffer sb = new StringBuffer("#");        for (int i = 0; i < len; i++) {            sb.append(s.charAt(i)).append("#");        }        String ss = sb.toString();        int len2 = ss.length();        for (int i = 1; i < len2; i++) {            int result = 1;            for (start = i - 1, end = i + 1; start >= 0 && end < len2 ; start--, end++) {                if(ss.charAt(start) == ss.charAt(end))                    result += 2;                else                    break;            }            if(maxLen < result) {                maxLen = result;                median = i;            }        }        String s2 = ss.substring(median - maxLen/2, median + maxLen/2 + 1);        return s2.replace("#", "");    }}

 　　

　　方法二：

　　　　回文子串分奇数、偶数长度两种情况。

　　

class Solution {    public String longestPalindrome(String s) {        int len = s.length();        if(len < 2)            return s;        int[] arr = new int[]{0,0};     // arr[0] = startIndex, arr[1] = maxLen;        for (int i = 0; i < len - 1; i++) {            findLongestPal(s, i, i, arr); // 奇数            findLongestPal(s, i, i+1, arr); // 回文子串为偶数        }        return s.substring(arr[0], arr[1] + arr[0]);    }    public void findLongestPal(String s, int start, int end, int[] arr) {        while(start >= 0 && end < s.length()                && s.charAt(start) == s.charAt(end)) {            end++;            start--;        }        if(arr[1] < end - start - 1) {  // 因为 while 中 多走了一步循环            arr[0] = start + 1;                 arr[1] = end - start - 1;        }    }}