本文共 1426 字，大约阅读时间需要 4 分钟。

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

示例 1：

输入：s = “babad”

输出：“bab” 解释：“aba” 同样是符合题意的答案。 示例 2：

输入：s = “cbbd”

输出：“bb” 示例 3：

输入：s = “a”

输出：“a” 示例 4：

输入：s = “ac”

输出：“a”

来源：力扣（LeetCode）

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

解题思路：1.如果字符串长度为1，那么一定是回文串

2.如果长度是2，那么两边相等即为回文串 3.如果长度大于等于3，两边界相等且出去两边界的子串是回文串 回文串说白了就是向外扩展，只要子串是回文串，然后保证两边相等，得到的新的一定是回文串，这就将大问题转化成了子问题来求解。用动态规划

代码如下：

public String longestPalindrome(String s) {
         //长度为1直接返回      if(s.length()<2){
             return s;      }      int maxlen=1;//默认最长为1，如果后来没有出现过大于1的，就直接返回首字母      int begin=0;      int len=s.length();      //设置一个标识状态的二维数组，dp[i][j]表示字符串从i到j是否是回文串      boolean[][]dp=new boolean[len][len];      //初始化所有长度为1的都是回文串     for(int i=0;i
   
    =len){
                   break;             }else{
                    if(s.charAt(i)!=s.charAt(j)){
                        dp[i][j]=false;//两边界不相等就不是回文串                 }else{
                    //两边相等，要分情况；一般是看子串是否是回文串，但是一定要判断，j-i==1的情况，比如dp[0][1]要根据dp[1][0]来判断，这是不对的                     if(j-i<2){
                              dp[i][j]=true;                     }else{
                            dp[i][j]=dp[i+1][j-1]；                     }                 }             }             if(dp[i][j] && (j-i+1)>maxlen){
                    maxlen=j-i+1;                 begin=i;             }         }     }     //一定要记住substring结尾处索引是不包括的！！！     return s.substring(begin,begin+maxlen);    }
   

转载地址：http://fcwuk.baihongyu.com/