最长回文（动态编程）代码因大型输入而超时。如何改善？

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设置为透视2.检查字符串是否是围绕枢轴的回文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 ('\0' != *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 || '\0' == right+1)
                {
                    break;
                }
                ++length;
            }

            return found;
        }
    };

    void TestPalin()
    {
        Solution solver;
        auto found = solver.longestPalindrome("123abba");
        std::cout << "PALINDROME = " << found << std::endl;
    }