寻找最长的回文子串（次优）

Question

我正在做一个编码练习，要求我在给定输入字符串时找到最长的回文子串。我知道我的解决方案在效率方面不是最优的，但我试图首先获得正确的解决方案。

到目前为止，这是我所拥有的：

#include <string>
#include <algorithm>
#include <iostream>

class Solution {
public:
    string longestPalindrome(string s) {
        string currentLongest = "";
        
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i; j <= s.length(); j++)
            {
                string testcase = s.substr(i, j);
                string reversestring = testcase;
                std::reverse(reversestring.begin(), reversestring.end());
                if (testcase == reversestring)
                {
                    if (testcase.length() > currentLongest.length())
                    {
                        currentLongest = testcase;
                    }
                }
            }
        }
        
        
        return currentLongest;
    }
};

它适用于多个测试用例，但在许多其他测试用例上也会失败。我怀疑在我的代码的最内层循环中出现了问题，但我不确定到底是什么。我试图生成所有可能的子串，然后通过将它们与它们的反向进行比较来检查它们是否是回文；在我确定它们是回文后，我检查它是否比我找到的当前最长回文更长。

Answer 1

因为您没有尝试所有可能的解决方案

在c++中，substr有两个参数，第一个是起始索引，第二个是子字符串的长度

在你的程序中，你怎么不检查从索引 4 开始并且长度为 3 的字符串，例如

在第二个 for 循环中你应该从索引 1 开始而不是从索引 i

寻找最长的回文子串（次优）

Finding the longest palindromic substring (suboptimally)

c++

substring

palindrome