进一步降低最长回文子串问题算法时间复杂度的方法

Question

第一次发帖在这里，如果我的 post/question 有任何问题，我们深表歉意。请让我知道，以便我进行调整。

我正在寻求一些帮助，以进一步改进我在 LeetCode 上找到的最长回文子串的解决方案，因为它在提交过程中总是 TLE。我认为算法是正确的，大约是 O(N^2)，我认为这是我应该拥有的，但显然它仍然太慢了。

我头疼的原因：https://leetcode.com/problems/longest-palindromic-substring

我不确定我可以使用哪些其他做法来优化它。我不认为 DP 也可以用于我的实现。但我可能是错的！另外，也许 std::string 的 equal 方法是 O(N)？但我觉得这不是我可以从我的解决方案中改变的东西。

欢迎任何反馈！

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()<2) 
            return s;
        int max=0;
        string p=s;
        int curr_pos=0;
        for(;curr_pos<s.length();curr_pos++){
            for(int i=max+1;i+curr_pos<=s.length();++i){
                string curr_s=s.substr(curr_pos,i);
                if(equal(curr_s.begin(), curr_s.begin() + curr_s.size()/2, curr_s.rbegin())){
                    p=curr_s;
                    max=curr_s.length();
                    i=max;
                }
            }
        }
        return p;
    }
};

Answer 1

你的解决方案在最坏的情况下似乎是 O(n^3)。

您可以使用 DP 并将先前计算的回文存储在 table 中。按子字符串长度的递增顺序填充 table。如果第一个和最后一个字符相同并且第一个和最后一个字符被剥离的字符串是回文，则该字符串是回文。

这个的复杂度是O(n^2)。

这是我的实现：

string longestPalindrome(string s) {
    vector table(s.size(), vector<bool>(s.size()));
    string_view sol{s.data(), 1};

    for (size_t i = 0; i < s.size(); ++i)
        table[i][i] = true;
    for (size_t i = 0; i < s.size() - 1; ++i) {
        auto cell = table[i][i+1];
        cell = s[i] == s[i+1];
        if (cell && sol.size() < 2)
            sol = {&s[i], 2};
    }
    for (size_t len = 3; len < s.size(); ++len) {
        for (size_t i = 0; i < s.size() - len + 1; ++i) {
            size_t last = i + len - 1;
            auto cell = table[i][last];
            cell = table[i+1][last-1] && s[i] == s[last];
            if (cell && len > sol.size())
                sol = {&s[i], len};
        }
    }

    return string(sol);
}

进一步降低最长回文子串问题算法时间复杂度的方法

Methods to further reduce time complexity of this algorithm for Longest Palindromic Substring problem

c++

palindrome