5. Longest Palindromic Substring

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.

String类题目

##Approach 1: Dynamic Programming 令P(i,j)表示子串s.substring(i,j+1)是否为回文子串。

则P(i,j)为true的条件为：P(i,j) = P(i+1,j-1) and (s[i] == s[j]) , i+2 <= j

base cases为：P(i,i) = true, P(i,i+1) = (s[i] == s[i+1])

时间复杂度为O(n^2)，空间复杂度为O(n^2)

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return null;
        }
        if(s.length() == 1)
            return s;
        int len = s.length();
        boolean[][] pTable = new boolean[len][len];
        int longestLen = 1;
        int left = 0, right = 0;
        for(int i = len-1; i >= 0; i--) {
            pTable[i][i] = true;
            for(int j = i+1; j < len; j++) {
                if(j == i+1) {
                    pTable[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    pTable[i][j] = (pTable[i+1][j-1] && (s.charAt(i) == s.charAt(j)));
                }
                if(pTable[i][j] == true && j-i+1 > longestLen) {
                    longestLen = j-i+1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left, right+1);
    }
}

##Approach 2: Expand Around Center 上面的方法的缺点在于需要额外的空间来存储n*n的表。

回文子串的特点是在center两边成镜像。 因此可以找出每个center，然后从两边延伸来找最长回文子串。 注意到对于一个长度为n的String，其实center有2n-1个，因为有center在两个字符之间。

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return null;
        }
        if(s.length() == 1)
            return s;
        int start = 0, end = 0;
        for(int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i+1);
            int len = Math.max(len1, len2);
            if(len > end-start+1) {
                start = i - (len-1)/2;
                end = i + len/2;
            }
        }
        
        return s.substring(start, end+1);
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right-left-1;
    }
}