最长回文子串

来源Leetcode第五题最长回文子串

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

输入: “babad”

输出: “bab”
注意: “aba” 也是一个有效答案。

又是一次常规暴力遍历找到答案，但是在第93个用例时超时了，查看官方解答，采用动态规划。
定义p(i,j),如果子串si到sj是回文子串，则p(i,j)为真，否则为假，可得p(i,j)=((p(i+1,j-1) and Si==Sj)。这样如果p(i,i)为真，则p(i,i+1)=(Si+1)。
求 长度为 1 和长度为 2 的 P(i,j) 时不能用上边的公式，因为我们代入公式后会遇到 P[i][j]中i >j的情况，比如求 P[1][2]的话，我们需要知道 P[1+1][2-1]=P[2][1]，而P[2][1]代表着S[2,1] 是不是回文串，显然是不对的，所以我们需要单独判断。
所以我们先初始化长度是1的回文串的P[i,j]，这样利用上边提出的公式，然后两边向外各扩充一个字符，长度为3的，为5的，所有奇数长度的就都求出来了。
同理，初始化长度是2的回文串P[i,i+1]，利用公式，长度为4的，6的所有偶数长度的就都求出来了。
时间复杂度：O(n^2)O
空间复杂度：O(n^2)，该方法使用 O(n^2)的空间来存储表。
附上代码：

class Solution {
    public String longestPalindrome(String s) {
       int length = s.length();
    boolean[][] P = new boolean[length][length];
    int maxLen = 0;
    String maxPal = "";
    for (int len = 1; len <= length; len++) //遍历所有的长度
        for (int start = 0; start < length; start++) {
            int end = start + len - 1;
            if (end >= length) //下标已经越界，结束本次循环
                break;
            P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); //长度为 1 和 2 的单独判断下
            if (P[start][end] && len > maxLen) {
                maxPal = s.substring(start, end + 1);
            }
        }
    return maxPal;
    }
}

但是这样效率还是很低，执行用时:906 ms, 在所有 Java 提交中击败了5.26%的用户，内存消耗:372.5 MB, 在所有 Java 提交中击败了5.00%的用户
但是从公式发现是从i+1才知道i，所以我们不妨试着倒着遍历，提供两个版本的代码：

   public String longestPalindrome(String s) {
		int n = s.length();
		String res = "";
		boolean[] P = new boolean[n];
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j >= i; j--) {
				P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
				if (P[j] && j - i + 1 > res.length()) {
					res = s.substring(i,j + 1);
				}
			}
		}
		return res;
	}
	
	
public String longestPalindrome(String s) {
    int n = s.length();
    String res = "";
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表长度减去 1        
            if (dp[i][j] &&  j - i + 1 > res.length()) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}

另一种思路是拓展中心，回文串一定是对称的，所以在每一次循环中选择一个中心，向左右拓展，判断两边字符是否相等。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    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) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private 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++;
    }
    return R - L - 1;
}

动态规划补充：

public String longestPalindrome(String s) {
    if(s.length() == 0 || s.length() < 2)
        return s;
    char[] arr = s.toCharArray();
    int len = arr.length;
    boolean[][] dp = new boolean[len][len];
    int maxLen = 1 , maxEnd = 0;  //注意maxLen初始化为1，因为单个字符一定是可以的
    for(int right = 1 ; right < len ; ++right){
        for(int left = 0 ; left < right ; ++left){
            if(arr[left] == arr[right] && (right - left <= 2 || dp[left+1][right-1])){
                dp[left][right] = true;
                if(right - left + 1 > maxLen){
                    maxLen = right - left + 1;
                    maxEnd = right;
                }
            }
        }
    }
    return s.substring(maxEnd - maxLen + 1 , maxEnd + 1);
}

最后一种Manacher’s Algorithm 马拉车算法先挖个坑吧，下次再看。