LeetCode每日一题，最长回文子串

题目

最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/java

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

描述

难度：中等学习

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

示例 1：.net

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

示例 2：code

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

示例 3：内存

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

示例 4：leetcode

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

提示：字符串

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

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%的用户

动态规划

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

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