原文链接：https://blog.csdn.net/qq_39355828/article/details/117232894 (opens new window)

【剑指Offer5】最长回文字符串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”

输出：“bab”

解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”

输出：“bb”

示例 3：

输入：s = “a”

输出：“a”

示例 4：

输入：s = “ac”

输出：“a”

提示：

1 <= s.length <= 1000

s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析:

如果字符串长度为0，则返回空字符串。

利用动态规划处理问题。dp是一个二维数组，dp[i] [j]表示字符串从第i个到第j个位置是否是回文字符串。

初始状态：dp对角线上都是true

状态转换方程： dp[i] [j]=dp[i+1] [j-1];

结束条件： i和j之间的距离小于2

代码：

class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<0)
            return "";
        int len=s.length();
        boolean [][] dp=new boolean[len][len];
        int max=1;//记录
        int start=0;
        char [] c=s.toCharArray();//转化成为数组之后，运算速率比较快
        for (int i=0;i<len;i++)
        {
            dp[i][i]=true;//初始化效果
        }
        for(int j=1;j<len;j++)//开始状态转换
        {
            for(int i=0;i<len-1&&i<j;i++)
            {
                if(c[i]!=c[j])//当两侧的不相等，则直接判定不是回文
                    dp[i][j]=false;
                else
                {
                    if(j-i<3)
                        dp[i][j]=true;
                    else
                        dp[i][j]=dp[i+1][j-1];

                }
                if(dp[i][j]&&j-i+1>max)
                {
                    max=j-i+1;
                    start=i;
                }
            }

        }
        return s.substring(start, start + max);
    }
}