题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述:

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

示例:

示例 1：

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"

输出: "bb"

思路:

三种思路:

1. 把每个字母当成回文串的中心

   这里要考虑两种情况,回文串的长度为奇数或者偶数情况.

2. 把每个字母当成回文串的结束

3. dp[i][j]表示字符串从j到i是否是为回文串,即当s[j] == s[i]如果dp[i-1][j+1]也是回文串,那么字符串从j到i也是回文串,即dp[i][j]为真

代码:

方法一:

class Solution:

    def longestPalindrome(self, s: str) -> str:

        n = len(s)

        self.res = ""

        def helper(i,j):

            while i >= 0 and j < n and s[i] == s[j]:

                i -= 1

                j += 1

            if len(self.res) < j - i -1 :

                self.res = s[i+1:j]

        for i in range(n):

            helper(i,i)

            helper(i,i+1)

        return self.res

方法二

class Solution:

    def longestPalindrome(self, s: str) -> str:

        if not s:

            return ""

        max_len = 1

        n = len(s)

        start = 0

        for i in range(1,n):

            even = s[i-max_len:i+1]

            odd = s[i - max_len-1:i+1]

            #print(even,odd)

            if i - max_len - 1 >= 0 and odd == odd[::-1]:

                start = i - max_len - 1

                max_len += 2

            elif i - max_len >=0 and even == even[::-1]:

                start = i - max_len

                max_len += 1

        #print(start,max_len)

        return s[start: start+max_len]

方法3

class Solution:

    def longestPalindrome(self, s: str) -> str:

        if not s :

            return ""

        res = ""

        n = len(s)

        dp = [[0] * n for _ in range(n)]

        max_len = float("-inf")

        #print(dp)

        for i in range(n):

            for j in range(i,-1,-1):

                if s[i] == s[j] and (i - j < 2 or dp[i-1][j+1]):

                    dp[i][j] = 1

                if dp[i][j] and  max_len < i - j + 1:

                    #print("i,j",i,j)

                    res = s[j:i+1]

                    max_len = i - j + 1

        return res

java

class Solution {

    public String longestPalindrome(String s) {

        int n = s.length();

        String res = "";

        boolean[][] dp = new boolean[n][n];

        for(int i = 0 ;i < n; i++){

            for(int j = i; j >= 0 ;j --){

                if(s.charAt(i) == s.charAt(j) && ( i - j < 2 || dp[i-1][j+1]))

                    dp[i][j] = true;

                if (dp[i][j] && (i - j + 1 > res.length())){

                    res = s.substring(j,i+1);

                }

            }

        }

        return res;

    }

}