最长的回文(动态编程)代码因大输入超时而失败.如何改进

Question

我最近正在学习解决LeetCode上的动态编程问题。手头的问题是在任何给定的字符串中找到最长的回文。我的代码适用于小尺寸的输入字符串。但是对于非常大的输入来说是失败的。期待改进它的想法。

代码：

#include <iostream>
#include <vector>
class Solution {
public:
std::string longestPalindrome(std::string s) {
std::vector<std::string> sequence;
std::string dummy, longest;
for(auto it = s.begin(); it < s.end(); it++){
dummy += *it;
for(auto  it2 = it+1; it2 < s.end(); it2++) {
dummy += *it2;
sequence.push_back(dummy);
}
dummy = "";
}
for(auto &item : sequence) {
for(auto it = item.rbegin(); it < item.rend(); it++) {
dummy += *it;
}
if(item == dummy && item.size() > longest.size()) {
longest = item;
}
dummy = "";
}
if (longest.empty())
longest += *s.begin();
return longest;
}
};
int main() {
Solution solver;
std::cout << solver.longestPalindrome("babadhabab") << std::endl;
return 0;
}

Answer 1

我做了一些代码，我认为它运行得很好
我不确定这个代码是否完美快速
但大多数输入数据都不是回文，所以我相信这个函数会很好地工作(算法(1.迭代每个字符并将char设置为pivot2.检查字符串是否是围绕枢轴的回文3.大多数输入数据不是回文，因此4.最差输入数据：所有输入数据具有相同的值，如"aaaaaaaaaa">

class Solution {
public:
std::string longestPalindrome(std::string const& input)
{
if (2 > input.length()) { return std::string(); }
char const* input_data = input.c_str();
int found_palindrome_max_len = 0;
char const* found_palindrome = nullptr;
char const* current = input_data+1;
while ('' != *current)
{
auto palindrome = is_palindrome(input_data, current, found_palindrome_max_len);
if (nullptr != palindrome) { found_palindrome = palindrome; }
++current;
}
if (nullptr == found_palindrome) { return std::string(); }
return input.substr(found_palindrome - input_data, found_palindrome_max_len);
}
char const* is_palindrome(char const* begin, char const* pivot, int& max_palindrome_len)
{
std::cout << "[BEGIN] pivot=" << *pivot << ", max_len = " << max_palindrome_len << std::endl;
bool is_odd_check = true; // ex) abcba (odd length)
bool is_even_check = true; // ex) abccba (even lenth)
int length = 1;
char const* left = nullptr;
char const* right = nullptr;
char const* found = nullptr;
while (true == is_odd_check || true == is_even_check)
{
if (true == is_even_check && 0 == length % 2)   // even length check
{
left = pivot - length/2 + 1;
right = pivot + length/2;
std::cout <<  "(even)length=" << length << ", pivot=" << *pivot <<", left=" << *left << ", right=" << *right << std::endl;
if (*left != *right)
{
std::cout << "is_even_check = false" << std::endl;
is_even_check = false;
}
else
{
if (length > max_palindrome_len)
{ 
found = left; max_palindrome_len = length;
std::cout << "max_palindrome_len = " << length << ", found=" << left << std::endl;
}
}
}
else if (true == is_odd_check && 1 == length % 2)// odd length check
{
left = pivot - length/2;
right = pivot + length/2;
std::cout <<  "(odd)length=" << length << ", pivot=" << *pivot <<", left=" << *left << ", right=" << *right << std::endl;
if (*left != *right)
{
std::cout << "is_odd_check = false" << std::endl;
is_odd_check = false;
}
else
{
if (length > max_palindrome_len)
{ 
found = left; max_palindrome_len = length;
std::cout << "max_palindrome_len = " << length << ", found=" << left << std::endl;
}
}
}
if (begin == left || '' == right+1)
{
break;
}
++length;
}
return found;
}
};
void TestPalin()
{
Solution solver;
auto found = solver.longestPalindrome("123abba");
std::cout << "PALINDROME = " << found << std::endl;
}