TitleDescription给定一个字符串s，找出s中最长的回文子串。示例示例1：输入：s="babad"输出："bab"解释："aba"也是符合题意的答案。示例2：输入：s="cbbd"输出："bb"示例3：输入：s="a"输出："a"示例4：输入：s="ac"输出："a"来源：forcebutton(LeetCode）链接：https://leetcode-cn.com/probl...，版权归灵口网络所有。思路与解决方案BruteforcecrackingBruteforcecracking就是判断每个子串是否是回文。判断每个字符是否为回文，比如用cbac判断，左右指针对称判断，相等则移到中间，继续判断，不相等则直接返回false。publicstaticStringlongestPalindrome(Strings){if(s==null||s.length()==0){returns;}字符串结果=s.substring(0,1);for(inti=0;iresult.length()){result=s.substring(i,j+1);}}}返回结果；}//判断每个子串是否为回文publicstaticbooleanjudge(Stringsource,intstart,intend){//对称轴比较while(start<=end){if(source.charAt(start)!=source.charAt(end)){返回假；}开始++；结尾-;}返回真；}BruteForce复杂度太高会超时，不推荐。中心展开法回文串总是中心对称的。使用暴力方式时，截取子串后进行判断。只有判断了所有的对称性，才能证明回文。不对称，前功尽弃。反之，我们不妨在每个点都尝试向两边扩展，这样只要有不匹配的地方，我们就可以及时停止序列。值得注意的是，中心展开法是如何找到中心的？3个字符有多少个中心？一共有五个中心，有的可能是两个字符的空隙，有的可能是字符。那么在设计的时候，我们用left和right来表示两个指针：left=right：对称中心是字符left+1=right：对称中心是两个字符之间的空隙具体实现如下：classSolution{//开始下标publicstaticintstart=-1;//最大长度publicstaticintmaxLen=0;publicStringlongestPalindrome(Strings){start=-1;最大长度=0;如果（s==null||s.length()==0）{返回“”；}for(inti=0;i=0&&rightmaxLen）{maxLen=大小；开始=左+1；}}}动态编程其实如果一个字符串是回文，那么它反之亦然，也就是说，它和它反后的字符串其实是完全匹配的，那么如果我们用一个字符串和它反后的字符串来一一统计匹配，是不是就可以得到它的结果呢？答案是肯定的！假设原字符串为s1，反转后的字符串为s2，字符串长度为n，我们用数组nums[n][n]记录匹配的次数，nums[i][j]表示s1[i]结尾的字符子串，和以s2[j]结尾的字符子串，两者匹配字符的最大值是当s1[i]==s2[j]时：如果i==0或j==0:nums[i][j]=1elsenums[i][j]=nums[i-1][j-1]+1;如果s1[i]！=s2[j]，那么nums[i][j]=0其实就是一个状态转移表达式，即nums[i][j]是怎么求解的呢？nums[i][j]取决于nums[i-1][j-1]是否匹配当前字符。如果当前字符不匹配，则直接赋值为0。只有当当前字符匹配时才需要查看前一个的匹配值nums[i-1][j-1]。以babad为例：最后两行的计算：实现代码如下：classSolution{publicstaticStringlongestPalindrome(Strings){if(s==null||s.length()==0){返回””;}if(s.length()==1){返回s;}intlen=s.length();Strings1=newStringBuffer(s).reverse().toString();int[][]nums=newint[len][len];int结束=0,最大值=0;for(inti=0;imax){if(len-i-1+nums[i][j]-1==j){end=j;最大值=nums[i][j];}}}}返回s.substring(end-max+1,end+1);}}关于作者【作者简介】：公众号【秦淮杂货店】作者秦淮，技术之路不是一蹴而就的，山高水远漫长，哪怕再慢，也绝不会停下。个人写作方向：Java源码分析、JDBC、Mybatis、Spring、redis、分布式、简知Offer、LeetCode等，认真写好每篇文章，不喜欢标题党，不喜欢我不能保证一切我写的是完全正确的，但我保证我写的一切都经过实践或搜索过资料。如有遗漏或错误，敬请指正。剑指提供所有问答PDF2020年我写了什么？开源编程笔记
