查找最长的回文子字符串(次优)

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开始