【LeetCode Hot 100 最长回文子串】

新年的刷的第一题，题目如下：

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

示例 1：

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

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。非商业转载请注明出处。

初始思路：

刚开始的想法是想每个字符开始向左右进行拓展，将全部的字符循环一遍，最后就可以找到最长的回文字符串。但自己感觉这种方法时间复杂度太高了，就没往下想了，唉，太不自信了。

答案思路：

答案写的非常详细，分了三种方法，第三种不讲，有点复杂，首先要说的是和自己初始子路类似的解法-中心扩展算法，废话不多说，直接上代码：

<,> getLongest( & s, left,(left>=&&right<s.size()&&s[left]==--++ {left+,right- longestPalindrome( start=,end=( i=;i<s.size();i++==getLongest(s,i,i+(right1-left1>end-==(right2-left2>end-== s.substr(start,end-start+

答案中介绍的第二种方法是动态规划，直接看代码：

 longestPalindrome( strReturn=( len=;len<s.size();len++( i=;i<s.size()-len;i++(len=== (len==+len]=s[i]==s[i++len]=dp[i+][i+len-]&&(s[i]==s[i+(dp[i][i+len]&&len+>=s.substr(i,len+

两种算法的时间和空间复杂度对比如下：

　　　　　　　　时间复杂度　　　　空间复杂度

中心扩展算法：    O（n*n）                  O（1）

动态规划：　　　O（n*n）　　　　　O(n*n)