题目

最长回文子串

描述

难度：中等

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

示例 1：

  输入：s = "babad"
 输出："bab"
 解释："aba" 同样是符合题意的答案。  

示例 2：

  输入：s = "cbbd"
 输出："bb"  

示例 3：

  输入：s = "a"
 输出："a"  

示例 4：

  输入：s = "ac"
 输出："a"  

提示：

1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成

Solution

中心扩散法

解题思路

• 都是回文数，这次是最长的回文数，并且包含字符串和数字，所以跟之前第五题的 回文数 ，完全是两个题，没有可借鉴的地方
• 最终的结果是需要在字符串中找到最长的回文数，那么我们可以假定从字符串的 每个字符 开始，都有 回文数 ，通过遍历整体字符串的长度，并且算出每个字符回文数的长度，最后比较最长的数即可
• 假定每个字符都是存在 回文数 的，那么只有两种情况，回文子串长度为奇数（如 aba ，中心是( b )）回文子串长度为偶数（如 abba ，中心是( b,b )
• 无论字符串 S 是奇数还是偶数，判断回文数从当前字符开始， M==N ，其中 M 为中心的开始， N 为相邻的数字，奇数时， MN 为同一个字符，偶数时， MN 为 M,N=(M+1) ，如果 S[M]==S[N] ，则进行扩散，使 M– , N++ ，继续判断 S[M–],S[N++] 的值，相等则继续 M–,N++ ，直到 S[M–],S[N++] 不相等或者超越边界( M<0 OR N > = S.length() )为止

CODE

  class Solution {
     public String longestPalindrome(String s) {
          int len = s.length();
          String res = "";
          //如果小于2，直接返回
          if(len < 2){
              return s;
          }
          for(int i =0;i<len ; i++){
             //奇数情况，两个均为i
             res = sub(s,i,i,res)
             //偶数情况，中心数为i,i+1
             res = sub(s,i,i+1,res);
          }
          return res;
     }
 
     public String sub(String s,int m,int n,String res){
         //m,n在范围内，并且s[m] == s[n]
         while(m>=0 && (n < s.length()) && (s.charAt(m) == s.charAt(n))){
             //扩散，对应--
             m--;
             //扩散,对应++
             n++;
         }
         //这里其实是(n-1)-(m+1)-1,在上面while之后，会m--以及n++,比实际位置偏差一位
         if((n-m-1) > res.length()){
             //截取m+1位置，到n-1的地方，上面while比实际位置偏差一位，所以m需要+1，n不需要-1
             res=s.substring(m+1,n);
         }
         return res;
     }
 }
 
   

复杂度

• 时间复杂度： O(N2) ， N 为字符串长度，每个字符串向外遍历最多可能 N 个
• 空间复杂度： O(1)

结果

• 执行用时： 37 ms, 在所有 Java 提交中击败了 76.50 %的用户
• 内存消耗： 39 MB, 在所有 Java 提交中击败了 58.36 %的用户

动态规划

第一次接触动态规划，很遗憾，看了半天的动态规划还是没能看明白，后续看明白补充进来

我曾在银色平原漫步,也曾在青草之河垂钓，这片土地认识我，我们若不坚强，就将灭亡