leetcode刷题记录第五题

时间：2020-04-09 10:07:49 阅读：48 评论：0 收藏：0 [点我收藏+]

题目：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

什么叫回文串？

如果一个字符串正着读和反着读是一样的，那它就是回文串。

此题有暴力破解法，即遍历所有子串来进比较，效率太低，比较优秀的解法有中心扩展法，动态规划法和“马拉车”法。我使用的是中心扩展法来进行解题。

解法如下：

class Solution {

public:

int getStr(string &s, int left, int right)

{

　　// 计算以left和right为中心的回文串长度

while(left>=0 && right<s.length() && s[left] == s[right])

{

left --;

right ++;

}

return right - left - 1;

}

string longestPalindrome(string s) {

int len = s.length();

if(len == 0 || len == 1)

return s;

int start = 0;

int end = 0;

int mlen = 0;

for(int i=0;i<len -1;i++)

{

int num1 = getStr(s,i,i);//一个元素为中心

int num2 = getStr(s,i,i+1);//两个元素的空隙为中心

mlen=max(max(num1,num2),mlen);

if(mlen>end-start+1)

{

start=i-(mlen-1)/2;//起点就是传入的这个点往左扩展的次数

end=i+mlen/2;

}

return s.substr(start,mlen);

}

};

中心扩展法的思路就是选中一个点，然后分别向两边扩展，直到左右两边扩展的字符不相等，返回总共扩展了的长度。

leetcode刷题记录第五题

原文：https://www.cnblogs.com/nelbuio/p/12664496.html

踩

(1)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)