字符串中最长的回文？

Question

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

输入

vnrtysfrzrmzlygfv

输出

v

预期产量

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);

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

1. 我通过引用

   ispalindrome

   函数
传递字符串
2. 我修改了算法来检查子串是否是回文。第一次不匹配后返回

   false

3. 我没有明确构建每个子字符串。我只将子字符串的开头和开头传递给辅助函数
4. 我首先检查是否存在最大尺寸的回文，然后减少它的长度。一旦找到回文，我们就知道它具有最大大小，我们就可以停止搜索

#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;
}

Answer 2

This might help:

static void Main(string[] args)
{

    var input = Console.ReadLine();
    while (input != null)
    {
        if (string.IsNullOrWhiteSpace(input))
        {
            Console.WriteLine("Input Can not be null");
            return;
        }

        var palindromeList = GetPalindromeList(input);
        var longestPalindrome = palindromeList.FirstOrDefault(p => palindromeList.Max(p => p.Length) == p.Length);

        Console.WriteLine(longestPalindrome??"No palindrome text found.");
        input = null;
        input = Console.ReadLine();
    }
   
}

private static string[] GetPalindromeList(string input)
{
    var inputSize = input.Length - 1;
    var list = new List<string>();
    for (var i =0 ; i < inputSize; i++)
    {
        var s = input[i];
        for (int j = i+1; j < input.Length; j++)
        {
            var e = input[j];
            if(s == e)
            {
                var len = j - i + 1;
                var sub = input.Substring(i, len);
                if (IsPalindrome(sub))
                {
                    list.Add(sub);
                }
            }
        }
    }
   
    return list.ToArray();
}

private static bool IsPalindrome(string input)
{
    var re = string.Empty;
    for (int i = input.Length - 1; i >= 0; i--)
    {
        re += input[i];
    }
    return input == re;
}