[LeetCode每日一题]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.

5. Longest Palindromic Substring 这道题让我们求给定字符串的最长回文子串。 第一种解法是动态规划。 设状态空间为二维布尔值数组dp[][],dp[i][j]表示字符串第i个字符到第j个字符是否是回文串。 状态转移方程设为

dp[i][i] = case i == j: ture
           case i + 1 == j: s[i]==s[j]
           default: 如果s[i]!=[j]值为false，如果s[i]==s[j]值为dp[i+1][j-1]

在求解的过程中，我们还要记录当前最长回文串开始的位置和结束的位置。 实现代码如下：

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int start = 0;
        int end = 0;
        int len = s.length();
        boolean dp[][] = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int subLen = 2; subLen <= len; subLen++) {
            for (int i = 0; i <= len - subLen; i++) {
                int j = i + subLen - 1;
                if (s.charAt(i) != s.charAt(j)) {
                    continue;
                }
                if (j - i == 1 || dp[i + 1][j - 1] == true) {
                    dp[i][j] = true;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}

该方法时间复杂度和空间复杂度均为O(n^2)。 第二种方法是中心扩散法，每个回文串均有一个中心，中心有两种情况，一是例如aba的情况，中心为a，二是例如abba的情况，中心是bb。因此遍历每种中心共有2n-1种情况，使用该算法时间复杂度降到O(n),空间复杂度为O(1)。 实现代码如下：

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int len = s.length();
        int start = 0;
        int end = 0;
        for (int i = 1; i < len; i++) {
            int subLen = Math.max(maxLength(s, i, i), maxLength(s, i - 1, i));
            if (subLen > end - start + 1) {
                start = i - subLen / 2;
                end = start + subLen - 1;
            }
        }
        return s.substring(start, end + 1);
    }

    private int maxLength(String s, int i, int j) {
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        return j - i - 1;
    }
}

第三种方法是Manacher's算法，可参考longest-palindromic-substring-part-ii