哇，这个题牛逼了，也做了一个下午。
其实就是给一个长串。然后找出最长的回文字串。
最开始想到的办法是暴力，反正做题嘛，先做出来再说。
怎么暴力呢，最开始的想法是：
一个固定的函数 check 判断该串是不是回文。
s 如果是，那么就是了。
不然 check(s(0,s.length()-2)) 和 s(1,s.length()-1)
这个代码写出来，然后试了试，很短的串没问题，但是仔细想想这个复杂度太高了，特别是串稍微长点点。
果然前期超时。
超时的话，就是方法不对，需要改思路。
那我们就逆思维：
先判断
s[i] 是不是回文，然后两边各+1
s[i] s[i+1] 是不是回文，然后两边各+1
之所以有两种情况是因为奇和偶的问题。
欧克，这样大部分情况应该时间会优化一些。
但还是超时，这样其实离成功更进一步了。
下面再接着想，其实每次不一定是+1，如果我当前已经找到了长为 sum 的串，那么枚举下一个节点的时候，其实我可以从+sum/2 来查询，果然 AC 啦~~~~~~~
WA 的几次就是边界没写好~~~~
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
|
class Solution {
public:
int sum;
int step;
string ans;
string longestPalindrome(string s) {
// Note: The Solution object is instantiated only once and is reused by each test case.
sum = 0;
for(int i = 0;i < s.length();i++)
{
step = sum/2;
if(i-step < 0 || i+step >= s.length())
continue;
func(s,i-step,i+step);
}
for(int i = 0;i < s.length();i++)
{
step = sum/2;
if(i-step < 0 || i+step+1 >= s.length())
continue;
func(s,i-step,i+1+step);
}
return ans;
}
void func(string s,int x,int y)
{
if(x < 0 || y > s.length()-1)return;
if(checkp(s.substr(x,y-x+1)))
{
if(sum < y-x+1)
{
sum = y-x+1;
ans = s.substr(x,y-x+1);
}
func(s,x-1,y+1);
}
}
bool checkp(string s)
{
int i = 0;
int j = s.length() - 1;
while(i <= j)
{
if(s[i] != s[j])
return false;
i++;
j--;
}
return true;
}
};
|