Home > Net >  Finding the longest palindromic substring (suboptimally)
Finding the longest palindromic substring (suboptimally)

Time:09-23

I'm working on a coding exercise that asks me to find the longest palindromic substring when given an input string. I know my solution isn't optimal in terms of efficiency but I'm trying to get a correct solution first.

So far this is what I have:

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

It works for several test cases, but also fails on a lot of other test cases. I suspect something is going wrong in the most inner loop of my code, but am not sure exactly what. I'm attempting to generate all possible substrings and then check if they are palindromes by comparing them with their reverse; after I establish they are a palindrome I check if it's longer than the current longest palindrome I have found.

CodePudding user response:

because you are not trying all the possible solution

in c , substr takes two parameters the first are the starting index , and the second is the length of the substring

how ever in you program you don't check for the string which starts at index 4 and have length of three for example

in the second for loop you shoud start from index 1 not from index i

  • Related