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

Question

Closed. This question is opinion-based。它当前不接受答案。












想改善这个问题吗？更新问题，以便 editing this post用事实和引用来回答。

12天前关闭。



Improve this question




如果我的帖子/问题有任何问题，这里的第一次海报很抱歉。请让我知道，以便我进行调整。
我正在寻找进一步改进我在LeetCode上找到的最长回文子字符串的解决方案的帮助，因为它在提交过程中始终为TLE。我认为算法是正确的并且在O(N ^ 2)左右，我认为这是我应该拥有的，但显然它仍然太慢。
我头疼的来源: https://leetcode.com/problems/longest-palindromic-substring
我不确定我可以使用哪些其他方法来优化它。我不认为DP也可以与实现一起使用。但是我可能是错的!另外，也许std::string的相等方法是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;
    }
};

最佳答案

在最坏的情况下，您的解决方案似乎是O(n ^ 3)。
您可以使用DP并将先前计算的回文数存储在表中。按子串长度的升序填充表。如果第一个和最后一个字符相同，则字符串为回文，而去除了第一个和最后一个字符的字符串为回文。
其复杂度为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);
}

关于c++ - 最长回文子串问题进一步降低该算法时间复杂度的方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64283192/

上一篇：c++ - (C++)为什么我的程序没有输出平均等待时间和超过1小时的平均时间？

下一篇：c++ - 从 Fortran 调用特定的 C++ DLL

相关文章：

PHP初学者回文脚本

java - 需要固定我的 Java 代码

c++ - 小数点后的数字 QTableView 委托(delegate)

c++ - 谁在使用 MFC 的 VERIFY 宏？

c++ - 在 spoj AP2 上得到错误答案

c++ - 如何获得 "hardware time"

c++ - Qt - 将文件拖放到 ListView 中

在c中比较两个具有相同名称的不同字符串

algorithm - 关于回文相关的算法

Python:搜索一个单词中最长的回文和一个单词/字符串中的回文

Answer 1

在最坏的情况下，您的解决方案似乎是O(n ^ 3)。
您可以使用DP并将先前计算的回文数存储在表中。按子串长度的升序填充表。如果第一个和最后一个字符相同，则字符串为回文，而去除了第一个和最后一个字符的字符串为回文。
其复杂度为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);
}