LeetCode Longest Palindromic Substring题解

思考这个问题,最初的想法是把所有的解都尝试一遍,然后找出最长的回文字符串,于是,我就用了递归,跑了一遍最初的实例,跑通了,然后很开心的去提交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class SolutionLongestPalindromicSubstring {
public:
bool isPalindromic(string s){
int length=s.length();
int pl=0;
int pr=length-1;

while (pl<pr){
if(s.at(pl)!=s.at(pr)){
return false;
}
pl++;
pr--;
}
return true;
}
string longestPalindrome(string s) {
if (s.length()==0){
return s;
}
int length=s.length();
int pl=0;
int pr=length;
if (pr>=pl&&isPalindromic(s.substr(pl,(pr-pl)))){
return s;
}
int currpl=pl;
int currpr=pr;
string max="";
string temp="";
if((++currpl)<=pr){
temp=max=longestPalindrome(s.substr(currpl,currpr-currpl));
}
if(temp.length()>max.length())
max=temp;
currpl=pl;
currpr=pr;
if((--currpr)>=currpl){
temp=longestPalindrome(s.substr(currpl,currpr-currpl));
}
if(temp.length()>max.length())
max=temp;
currpl=pl+1;
currpr=pr-1;
temp=longestPalindrome(s.substr(currpl,currpr-currpl));
if(temp.length()>max.length())
max=temp;

return max;
}

};

结果,哦吼,超时了。

是啊,递归的复杂度太高了,然后,如果是我,肯定是从大的开始找啊。

顺着这个思路,再加上子串肯定是连续的,这么一想,然后就自动的去捆绑子串。

首先捆绑的子串的长度就是原串本身,如果是回文,则最长的子串就找到啦。

如果捆绑串不是回文,则捆绑的长度-1,再从左往右移动,依次检验当前捆绑串是否是回文子串

重复上诉步骤,肯定能找到回文串,毕竟一个字符也是回文子串嘛

贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class SolutionLongestPalindromicSubstring{
public:
bool isPalindromic(string s){
int length=s.length();
int pl=0;
int pr=length-1;

while (pl<pr){
if(s.at(pl)!=s.at(pr)){
return false;
}
pl++;
pr--;
}
return true;
}
string longestPalindrome(string s){
if(isPalindromic(s))
return s;

int maxLength=s.length()-1;
int length=s.length();
int pl=0;
while (maxLength>1){
while (pl+maxLength<=length){
if(isPalindromic(s.substr(pl,maxLength))){
return s.substr(pl,maxLength);
}
pl++;
}
maxLength--;
pl=0;
}
return s.substr(0,1);

}
};

代码地址:

https://github.com/DuWenLi-mumu/LeetCodeSolution/blob/master/Longest%20Palindromic%20Substring.cpp