5年的感情终于要结束了 (转载)# Joke - 肚皮舞运动
n*r
1 楼
用的方法就是最简单的逆序+ longest common substring （DP）
judge small能过
judge large就提示说memory limit exceeded。
我DP的table是用vector存的， code如下，请大侠们给点儿建议。 提前谢谢啦！
string longestPalindrome(string s) {
string ret;
if(s.empty())
return ret;
string s_copy = s;
reverse(s_copy.begin(), s_copy.end());
return findLongestCommonSubsequence(s, s_copy);
}
string findLongestCommonSubsequence(string s1, string s2){
int m = (int) s1.length();
int n = (int) s2.length();
vector > table;
for(int i = 0; i < m; i++){
vector r(n, 0);
table.push_back(r);
}
int maxLength = 0;
int r = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(s1[i]==s2[j]){
if(i!=0&&j!=0)
table[i][j] = table[i-1][j-1] + 1;
else
table[i][j] = 1;
if(table[i][j] > maxLength){
maxLength = table[i][j];
r = i;
}
}
}
}
string ret;
if(maxLength!=0)
ret = s1.substr(r-maxLength+1, maxLength);
return ret;
}
judge small能过
judge large就提示说memory limit exceeded。
我DP的table是用vector存的， code如下，请大侠们给点儿建议。 提前谢谢啦！
string longestPalindrome(string s) {
string ret;
if(s.empty())
return ret;
string s_copy = s;
reverse(s_copy.begin(), s_copy.end());
return findLongestCommonSubsequence(s, s_copy);
}
string findLongestCommonSubsequence(string s1, string s2){
int m = (int) s1.length();
int n = (int) s2.length();
vector
for(int i = 0; i < m; i++){
vector
table.push_back(r);
}
int maxLength = 0;
int r = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(s1[i]==s2[j]){
if(i!=0&&j!=0)
table[i][j] = table[i-1][j-1] + 1;
else
table[i][j] = 1;
if(table[i][j] > maxLength){
maxLength = table[i][j];
r = i;
}
}
}
}
string ret;
if(maxLength!=0)
ret = s1.substr(r-maxLength+1, maxLength);
return ret;
}
