a***e
发帖数: 413 | 1 听说是经典题，好多种解法。Bruteforce的最容易，O（N^2）的比较难想。暂时不太明
白DP。。。。。。。 |
q********c
发帖数: 1774 | 2 贴一个我的DP:
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int maxLen = 0, start=0;
bool S[1001][1001];
for(int i = n-1; i >=0; i--) {
for(int j = i; j < n; j++) {
S[i][j] = false;
if(s[i] == s[j] && ((j-i<2)||S[i+1][j-1])) {
S[i][j] = true;
if(j-i+1>maxLen) {
maxLen = j-i+1;
start = i;
}
}
}
}
return s.substr(start, maxLen);
}
};
【在 a***e 的大作中提到】
: 听说是经典题，好多种解法。Bruteforce的最容易，O（N^2）的比较难想。暂时不太明
: 白DP。。。。。。。
|
r****7
发帖数: 2282 | 3 如果是substring而不是subsequence的话，bruteforce最好吧。
【在 a***e 的大作中提到】
: 听说是经典题，好多种解法。Bruteforce的最容易，O（N^2）的比较难想。暂时不太明
: 白DP。。。。。。。
|
s*******y
发帖数: 12 | 4
DP无非就是用空间换时间, 先试着找找有没有递推关系吧.
【在 a***e 的大作中提到】
: 听说是经典题，好多种解法。Bruteforce的最容易，O（N^2）的比较难想。暂时不太明
: 白DP。。。。。。。
|
s*******y
发帖数: 12 | 5 为啥? bruteforce要O(N^3)效率实在受不了吧...
【在 r****7 的大作中提到】
: 如果是substring而不是subsequence的话，bruteforce最好吧。
|
r****7
发帖数: 2282 | 6 题是啥？是说找一个string里最长的palindromic substring吗？那不就是以每一个点
为中心，向两边走然后对比么？为什么不是N^2而是N^3?
不过我觉得可能有类似KMP的O(N)的算法
【在 s*******y 的大作中提到】
: 为啥? bruteforce要O(N^3)效率实在受不了吧...
|
r****s
发帖数: 1025 | 7 这尼玛不是讨论了无数遍了？
suffix trie是最简单的解决方法。 |
r*******k
发帖数: 1423 | 8 不是啥manacher算法吗？
【在 r****s 的大作中提到】
: 这尼玛不是讨论了无数遍了？
: suffix trie是最简单的解决方法。
|
y*******8
发帖数: 112 | |
a***e
发帖数: 413 | 10 我写了一个类似brute force的方法，请问这个应该算是O（N^2)么？多谢！
string extractor(string &s, int l,int ri)
{
string r;
int left=l,right=ri;
int len=s.length();
while(left>=0&&right
{
if (s[left]==s[right])
{
left--;
right++;
}
else
break;
}
r = s.substr(left+1,right-left-1);
return r;
}
string longestPalindrome(string s) {
int len = s.size();
if (len==0||len==1)
return s;
string longest = s.substr(0,1);
for (int i=1;i
{
string sub = extractor(s,i-1,i);
if (sub.length()>longest.length())
longest = sub;
string sub2 = extractor(s,i-1,i+1);
if (sub2.length()>longest.length())
longest = sub2;
}
return longest;
} |
