Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
这也是《算法导论》中的一个练习题，先给一个自己想的算法（最坏情况的时间复杂度为O(n2)）：
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() == 0)
return 0;
int i = 0, j = s.size() - 1;
int flag = 0;
int subscript = j;
string s1 = "";
while (i < j)
{
while (i < j)
{
if (s[i] == s[j])
{
s1 += s[j];
subscript = --j;
i++;
flag = 1;
break;
}
j--;
flag = 0;
}
if (!flag)
{
j = subscript;
i++;
}
}
int k = 0, l = s.size() - 1;
flag = 0;
subscript = l;
string str = s;
reverse(str.begin(), str.end());
string s2 = "";
while (k < l)
{
while (k < l)
{
if (str[k] == str[l])
{
s2 += str[l];
subscript = --l;
k++;
flag = 1;
break;
}
l--;
flag = 0;
}
if (!flag)
{
l = subscript;
k++;
}
}
int l1 = s1.size(), l2 = s2.size();
s1 = l2 > l1 ? s2 : s1;
if (i >= k && i > j)
{
string str = s1;
reverse(str.begin(), str.end());
s1 += str;
}
else if (k > i && k > l)
{
string str = s1;
reverse(str.begin(), str.end());
s1 += str;
}
else
{
string str = s1;
reverse(str.begin(), str.end());
s1 += s[l1 >= l2 ? i : k];
s1 += str;
}
return s1;
}
};
两段二重循环的目的是：第一段从右到左缩短str来得到回文子串s1；第二段将原来的字符串反转，然后同样的方式得到一个回文子串s2，然后返回最长的。
但结果Leetcode以这种方式拒绝了：
Input: "abcda" Output: "ada" Expected: "a"
但我不觉得我的错了啊...书上说：character，返回：carac，但在Leetcode竟然错了。。。看来和书上问题并不太一样。
完整代码（可以返回最长回文子串的长度）：
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
class Solution {
public:
std::string LPS(std::string str)
{
if (str.size() == 0)
return 0;
int r1 = 1;
int i = 0, j = str.size() - 1;
int flag = 0;
int subscript = j;
std::string s1 = "";
while (i < j)
{
while (i < j)
{
if (str[i] == str[j])
{
s1 += str[j];
subscript = --j;
i++;
r1++;
flag = 1;
break;
}
j--;
flag = 0;
}
if (!flag)
{
j = subscript;
i++;
}
}
int r2 = 1;
int k = 0, l = str.size() - 1;
flag = 0;
subscript = l;
std::string s = str;
std::reverse(s.begin(), s.end());
std::string s2 = "";
while (k < l)
{
while (k < l)
{
if (s[k] == s[l])
{
s2 += s[l];
subscript = --l;
k++;
r2++;
flag = 1;
break;
}
l--;
flag = 0;
}
if (!flag)
{
l = subscript;
k++;
}
}
int l1 = s1.size(), l2 = s2.size();
s1 = l2 > l1 ? s2 : s1;
if (i >= k && i > j)
{
std::string s = s1;
std::reverse(s.begin(), s.end());
s1 += s;
r1--;
}
else if (k > i && k > l)
{
std::string s = s1;
std::reverse(s.begin(), s.end());
s1 += s;
r2--;
}
else
{
std::string s = s1;
std::reverse(s.begin(), s.end());
s1 += str[l1 >= l2 ? i : k];
s1 += s;
}
r1 *= 2;
r1 = i > j ? r1 : r1 - 1;
r2 *= 2;
r2 = k > l ? r2 : r2 - 1;
r1 = l1 >= l2 ? r1 : r2;
std::cout << r1 << std::endl;
return s1;
}
};
int main()
{
Solution solve;
std::string str = "abcda";
std::cout << str << std::endl;
std::cout << solve.LPS(str) << std::endl;
getchar();
return 0;
}
最开始我想到的办法是通过反转s，得到字符串s‘，然后把问题转化成求LCS，但我发现不符合书上要求。但看样子，Leetcode的问题可以用这个方法解决。dp解法我还不会。。。没得到最优子结构，所以推不出递归式...emmm...但我的这个算法可以解决书上的这个问题，平均情况是很快的：我估计能在O(nlgn)以内，最好情况下为：O(n)；但最坏情况下，比如：abcdef这类的就是O(n2)。