【题目】
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
【思路】
暴力破解:得到所有子串,判断是否为回文子串。时间复杂度为O(n^3)。
可以想到,有很多子串是根本不必判断的。
我们以某个元素(下标为i)为中心,依次判断i-1和i+1,i-2和i+2是否相等,若不相等,则得到以该元素为中心的最长回文子串。可以称该回文子串为“aba”模式。
还有一种回文子串模式,即“baab”模式。我们以某两个元素(下标为i,i+1)为中心,依次判断i-1和i+2,i-2和i+3是否相等,若不相等,得到以该两个元素为中心的最长回文子串。
循环遍历所有元素,即可得到整个字符串的最长回文子串。时间复杂度为O(n^2)。
【代码】
python版本
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
length = len(s)
if length < :
return ""
res = ""
for i in range(, length):
# "aba"类型,回文子串元素个数为奇数
tmp =
m = i -
n = i +
while m >= and n < length and s[m] == s[n]:
tmp +=
m -=
n +=
if len(res) < tmp:
res = s[m+:n]
# "baab"类型,回文子串元素个数为偶数
tmp =
m = i
n = i +
while m >= and n < length and s[m] == s[n]:
tmp +=
m -=
n +=
if len(res) < tmp:
res = s[m+:n]
return res
C++版本
class Solution {
public:
string longestPalindrome(string s) {
int m=, n=;
int tmp=;
string res="";
for(int i=; i<s.size(); i++){
// "aba"模式
tmp = ;
m = i - ;
n = i + ;
while(m>= && n<s.size() && s[m] == s[n]){
tmp += ;
m--;
n++;
}
if(res.size() < tmp){
res = s.substr(m+, tmp);
}
// "baab"模式
tmp = ;
m = i;
n = i + ;
while(m>= && n<s.size() && s[m] == s[n]){
tmp += ;
m--;
n++;
}
if(res.size() < tmp){
res = s.substr(m+, tmp);
}
}
return res;
}
};