LeetCode5- 最长回文子串(Longest Palindromic Substring)

本文主要是介绍LeetCode5- 最长回文子串(Longest Palindromic Substring)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode5- 最长回文子串(Longest Palindromic Substring)

最近全国疫情严重，待在家里没事干，马上又要准备春招了，最近刷刷题，记录一下！再说一句，武汉加油，大家出门记得戴口罩！

1、题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例：

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

2、思路

暴力枚举O(n2)
由于字符串长度小于1000，因此我们可以用 O(n2) 的算法枚举所有可能的情况。
首先枚举回文串的中心 i，然后分两种情况向两边扩展边界，直到遇到不同字符为止:

回文串长度是奇数，则依次判断 s[i−k]==s[i+k],k=1,2,3,…
回文串长度是偶数，则依次判断 s[i−k]==s[i+k−1],k=1,2,3,…
如果遇到不同字符，则我们就找到了以 i
为中心的回文串边界。
时间复杂度分析：一共两重循环，所以时间复杂度是 O(n2)
。

3、代码

class Solution {
public:string longestPalindrome(string s) {string res;for(int i=0;i<s.size();i++){int j,k; //j往左，k往右for(int j=i,k=i;j>=0&&k<s.size()&&s[j]==s[k];j--,k++){if(res.size()<k-j+1){//获得字符串s中从第0位开始的长度为5的字符串res=s.substr(j,k-j+1);}}for(int j=i,k=i+1;j>=0&&k<s.size()&&s[j]==s[k];j--,k++){if(res.size()<k-j+1){res=s.substr(j,k-j+1);}}}return res;   }
};