字符串中最长的回文？

Question

我想打印字符串中最长的回文，我已经编写了代码，但这对某些测试用例给出了错误的答案。我无法在我的代码中找到错误。任何人帮助我，任何帮助将不胜感激。

输入

vnrtysfrzrmzlygfv

输出

预期输出

rzr

代码：

class Solution {
public:
    int ispalindrome(string s)
    {
        string rev = "";
        int n = s.size();
        for (int i = n - 1; i >= 0; i--) {
            rev = rev + s[i];
        }
        if (rev == s) {
            return 1;
        }
        return 0;
    }
    string longestPalin(string S)
    {
        // code here
        int size = S.size();
        int size_of_substr = 0;
        string ans;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                string s2 = S.substr(i, j);
                if (ispalindrome(s2)) {
                    if (s2.size() > size_of_substr) {
                        ans = s2;
                        size_of_substr = s2.size();
                    }
                    else {
                        continue;
                    }
                }
                else {
                    continue;
                }
            }
        }
        return ans;
    }
};

Answer 1

您使用的 substr(.) 不正确。第二个参数是子字符串的大小。

string s2 = S.substr(i, j); 应替换为 string s2 = S.substr(i, j-i+1);

而且，这段代码效率不会很高。为了加快速度，我按以下方式修改了您的代码：

我通过引用 ispalindrome 函数
我修改了算法来检查子串是否是回文。它returns false 先不匹配
我没有显式构建每个子字符串。我只将子字符串的开头和开头传递给辅助函数
我首先检查是否存在最大大小的回文，然后我减少它的长度。一旦找到回文，我们就知道它有最大长度，我们可以停止搜索

#include <iostream>
#include <string>

class Solution {
public:
    int ispalindrome(const std::string& S, int i, int j) {
        while (i < j) {
            if (S[i++] != S[j--]) return 0;
        }
        return 1;
    }
    std::string longestPalindrome(const std::string& S) {
        int size = S.size();
        int imax = 1;
        for (int size_of_substr = size; size_of_substr > 0; size_of_substr--, imax++) {
            int j = size_of_substr - 1;
            for (int i = 0; i < imax; i++, j++) {
                if (ispalindrome(S, i, j)) {
                        std::string ans = S.substr(i, size_of_substr);
                        return ans;
                }
            }
        }
        return "";
    }
};

int main() {
    Solution sol;
    std::string S;
    std::cin >> S;
    auto ans = sol.longestPalindrome(S);
    std::cout << ans << "\n";
    return 0;
}

字符串中最长的回文？

Longest palindrome in a string?

c++

string

class

function

palindrome