20200329
Plan
leetcode 每日一题 5. 最长回文子串
Notes
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
输入: "cbbd" 输出: "bb"
解法一： 暴力法 从长到短遍历s的每个子串，判断子串是否是回文，是的话返回。 时间复杂度： 这种方法最坏情况下共1+2+...+n=n(n+1)/2=O（n^2）个子串，每个子串判断回文需要O（n），故总的时间复杂度为O（n^3） 空间复杂度： 不需要额外空间，空间复杂度O（1）
解法二： 动态规划 用P（i,j）表示子串s[i:j+1]是否为回文，则P（i,j）=true,当p(i+1,j-1)==true而且第i个字符等于第j个字符；否则P（i,j）=false.故可初始化所有长度为1和长度为2的子串是否为回文。然后依次判断长度为3，长度为4,...的子串。最后返回是回文的最长的任意子串。 时间复杂度： 初始化的时间复杂度为O（n），遍历子串共1+2+...+n=n(n+1)/2=O（n^2）个子串，总的时间复杂度为O（n^2） 空间复杂度： 需要用二维数组额外记录每个子串是否为回文，故空间复杂度为O（n^2）
解法三： 中心扩展法 从头到尾遍历字符串，对每个字符，向左右两边扩展判断回文的最大长度。需要注意的是，每个字符都需要判以该字符为中心的子串以及以该字符右侧空隙为中心的子串。比如说对字符串"aba"，回文中心处于字符b；而字符串"abba"，回文中心处于两个b的中间空隙。 时间复杂度： 除了最后一个字符，每个字符都要判断自己和右侧空隙，故共2n-1个中心，每个中心左右扩展的时间复杂度为O（n），故总的时间复杂度为O（n^2） 空间复杂度： 不需要额外空间，空间复杂度O（1）