5. 最长回文子串
题目来源:https://leetcode-cn.com/problems/longest-palindromic-substring/
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例 1:
输入: “babad”
输出:”bab”
注意:”aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
解法
C++代码:
解法一:暴力破解法(菜 鸡 必 会 法)||( LeetCode 不 能 A C)
class Solution {
public:
string longestPalindrome(string s) {
int start=0,end=0;
for(int i=0;i<s.length();i++)
{
for(int j=i;j<s.length();j++)
{
string t=s.substr(i,j-i+1);
if(ifPalindromic(t))
{
if(j-i>end-start)
{
start=i;end=j;
}
}
}
}
string ret=s.substr(start,end-start+1);
return ret;
}
bool ifPalindromic(string s){ //判断是否是回文
for(int i=0;i<s.length()/2;i++)
if(s[i] != s[s.length()-1-i])
return false;
return true;
}
};
复杂度分析:
时间复杂度:O(n3)
空间复杂度:O(1)
解法二:中心扩散算法
暴力破解在很多场合往往是最容易想到的方法,但是通常在复杂度方面表现很差,效率很低下。
本题最容易想到的就是中心扩散算法。
中心扩散算法顾名思义就是从中心往两边逐步判断,但存在以下两种情况:
case 1: 中间值与左侧或者右侧任一侧相同,需要将相同一侧的指针往同方向移动
case 2: 中间值与两侧值都不相同,直接比较两侧值是否相同即可
下举例说明中心扩散算法:
left↓start↓right | ||||||
---|---|---|---|---|---|---|
e | c | b | a | a | b | d |
Step 1: 首先left指针左移一位。
left↓ | start↓right | |||||
---|---|---|---|---|---|---|
e | c | b | a | a | b | d |
判断 start==left?是则left继续左移一位,否则保持不变。
left↓ | start↓right | |||||
---|---|---|---|---|---|---|
e | c | b | a | a | b | d |
Step 2: right指针右移一位。
left↓ | start | ↓right | ||||
---|---|---|---|---|---|---|
e | c | b | a | a | b | d |
判断 start==right?是则right继续右移一位,否则保持不变。
left↓ | start | ↓right | ||||
---|---|---|---|---|---|---|
e | c | b | a | a | b | d |
Step 3: 判断right==left?是则left–,right++;否则跳出循环。
left↓ | start | ↓right | ||||
---|---|---|---|---|---|---|
e | c | b | a | a | b | d |
此时left!=right,所以返回(left+1,right-1)
因此该轮次得到的回文子串为baab
.
实现:
class Solution {
public:
string longestPalindrome(string s) {
int left,right;
int start=0,len,maxlen=1;
for(int i=0;i<s.length();i++)
{
left=i-1;
right=i+1;
len=1;
while(left>=0&&s[i]==s[left])
{
left--;
len++;
}
while(right<s.length()&&s[i]==s[right])
{
right++;
len++;
}
while(left>=0&&right<s.length()&&s[left]==s[right])
{
left--;
right++;
len+=2;
}
if(len>maxlen)
{
start=left+1;
maxlen=len;
}
}
string t=s.substr(start,maxlen);
return t;
}
};
执行用时 :108 ms, 在所有 C++ 提交中击败了57.47%的用户
内存消耗 :6.6 MB, 在所有 C++ 提交中击败了100.00%的用户
复杂度分析:
时间复杂度:
O(n^2)
空间复杂度:
O(1)