寻找最长的回文子串(次优)
Finding the longest palindromic substring (suboptimally)
我正在做一个编码练习,要求我在给定输入字符串时找到最长的回文子串。我知道我的解决方案在效率方面不是最优的,但我试图首先获得正确的解决方案。
到目前为止,这是我所拥有的:
#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;
}
};
它适用于多个测试用例,但在许多其他测试用例上也会失败。我怀疑在我的代码的最内层循环中出现了问题,但我不确定到底是什么。我试图生成所有可能的子串,然后通过将它们与它们的反向进行比较来检查它们是否是回文;在我确定它们是回文后,我检查它是否比我找到的当前最长回文更长。
因为您没有尝试所有可能的解决方案
在c++中,substr有两个参数,第一个是起始索引,第二个是子字符串的长度
在你的程序中,你怎么不检查从索引 4 开始并且长度为 3 的字符串,例如
在第二个 for 循环中你应该从索引 1 开始而不是从索引 i
我正在做一个编码练习,要求我在给定输入字符串时找到最长的回文子串。我知道我的解决方案在效率方面不是最优的,但我试图首先获得正确的解决方案。
到目前为止,这是我所拥有的:
#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;
}
};
它适用于多个测试用例,但在许多其他测试用例上也会失败。我怀疑在我的代码的最内层循环中出现了问题,但我不确定到底是什么。我试图生成所有可能的子串,然后通过将它们与它们的反向进行比较来检查它们是否是回文;在我确定它们是回文后,我检查它是否比我找到的当前最长回文更长。
因为您没有尝试所有可能的解决方案
在c++中,substr有两个参数,第一个是起始索引,第二个是子字符串的长度
在你的程序中,你怎么不检查从索引 4 开始并且长度为 3 的字符串,例如
在第二个 for 循环中你应该从索引 1 开始而不是从索引 i