Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example

Given the string = "abcdzdcab", return "cdxdc".

思路 1

因?yàn)橛蠸tring有偶數(shù)奇數(shù)長度之分，所以不能直接對String基于每個(gè)字母進(jìn)行判斷喧笔。
需要對其進(jìn)行插板操作瓶摆，比如 # a # b # b # c # 或者 # a # b # c# 這樣填充之后邓梅，奇偶長度的字符串都變成了偶數(shù)長度的字符串（從0開始）

1. 從左到右依次每個(gè)字母進(jìn)行判斷
2. 從每個(gè)字母左右延伸，知道判斷到其為回文則停止，得到該subString和回文長度
   • 判斷是否回文，判斷String(i - count) == String (i + count)。 如果 i - count為偶數(shù)則代表破花，其為#谦趣， 若為奇數(shù)則其為String(i-count/2)的字母
3. 如果得到了更長的substring回文長度，更新該長度和substring

public class Solution {
    /*
     * @param s: input string
     * @return: the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        // write your code here
        // 思路： 1. 從左到右挨個(gè)字母判斷
        // 2. 從每個(gè)字母左右延伸座每，直到判斷其非回文則停止前鹅，得到該substring的回文長度

        if (s == null || s.length() <= 1) {
            return s;
        }
        
        int len = s.length();
        int count = 0;
        int maxLen = 0;
        String result = null; 
        
        for (int i = 0; i < 2 * len - 1; i++) {
            count = 1;
            while (i - count >= 0 && i + count <= 2 * len && getChar(i - count, s) == getChar(i + count, s)) {
                count++;
        //         System.out.print(i);
        //         System.out.print(count);
        //         System.out.print(getChar(i - count, s));
        //         System.out.print(getChar(i + count, s));
            }
            count--;
            if (count > maxLen) {
                maxLen = count;
                result = s.substring((i - count) / 2, (i + count) / 2);
                count = 0;
            }
        }
        return result;
    }
    
    private Character getChar(int i, String s) {
        if (i % 2 == 0) {
            return '#';
        } else {
            return s.charAt(i / 2);
        }
    }

}

Solution 2

class Solution {
    public String longestPalindrome(String s) {
        // corner case
        if (s == null || s.length() == 0 || s.length() == 1) 
            return s;
        int[] max = new int[2];
        for (int i = 0; i + 1 < s.length(); ++ i) {
            int[] range = getLongestPalindrome(s, i, i);
            if (range[1] - range[0] > max[1] - max[0]) {
                max = range;
            }
            range = getLongestPalindrome(s, i, i + 1);
            if (range[1] - range[0] > max[1] - max[0]) {
                max = range;
            }
        }
        return s.substring(max[0], max[1] + 1);
    }
    
    private int[] getLongestPalindrome(String s, int left, int right) {
        int[] res = new int[2];
        int last = s.length() - 1;
        while (left >= 0 && right <= last && s.charAt(left) == s.charAt(right)) {
            -- left;
            ++ right;
        }
        res[0] = left + 1;
        res[1] = right - 1;
        return res;
    }
}