【leetcode刷题】T59-最长回文子串
【题目】
给定一个字符串 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;
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读