题目最长回文子串

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

难度：中等

给你一个字符串 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;     } }  

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

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