Longest Palindromic Substring
简介:字符串中最长的回文字符串
回文字符串:中心对称的字符串 ,如 mom,noon
问题详解:
给定一个字符串s,寻找字符串中最长的回文字符串,假设字符串s长度最长为1000.
举例:
1:
输入: “babad”
输出: “bab”
注: “aba” 也是一种答案.
2:
输入: “cbbd”
输出: “bb”
官方实现 : Expand Around Center
我们可以从字符串中心寻找回文字符串,例如"aba"的中心为’b’,"baab"的中心为两个a中间,所以分两种情况考虑,一种是中心为i,另一种是i和i+1,这里我们需要注意的是String里的方法substring(index start,index end),第二个s是小写的,并且是从start开始一直到end结尾但不包含end索引处的字符,所以我们要end+1
复杂度分析
时间复杂度分析 : O(n^2).
空间复杂度 : O(1).
小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海