题目描述

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

我的解法——DP（AC）

复杂度O(n2)
结果：Beat 21.24%

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        dp = [[-1 for j in range(length)] for i in range(length)]
        res = ''
        
        for i in range(length):
            dp[i][i] = 1

        for j in range(length):
            now = j
            for i in range(j - 1,-1,-1):
                if(s[i] == s[j]):
                    if(i + 1 == j or dp[i + 1][j - 1] == 1):
                        dp[i][j] = 1
                        now = i

                else:
                    dp[i][j] = 0

            if(len(res) < j - now + 1):
                res = s[now:j + 1]
        return res

# 最优解法——中心拓展法

遍历字符串的每一个字符，如果存在回文子串，那么中心是某一个字符（奇数）或两个字符的空隙（偶数），然后分两种情况（奇数或偶数）向两边扩展。
总时间O(n2)，空间O(1)，每次算法运行时间是O(2n-1)

public String longestPalindrome(String 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) {
            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;
}

其他解法——最长公共子串

将s翻转生成s’，找到s和s’之间的最长公共子串，就是最长回文。（66666）
大多数如：s=’caba’就能满足要求；但是如：s=’abacdfgdcaba’不能满足要求。
- 解决：检查下标
时间O(n2)，空间O(n2)。

private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

public NumArray(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            map.put(Pair.create(i, j), sum);
        }
    }
}

public int sumRange(int i, int j) {
    return map.get(Pair.create(i, j));
}

参考答案

https://leetcode.com/problems/longest-palindromic-substring/solution/