CODEWITHSUNDEEP
c++algorithmdynamic-programmingpalindrome
Devang Mukherjee
Devang Mukherjee

Reputation: 197

Longest palindromic substring missing an edge case

This is code I have written using dynamic programming concepts.

bool ispalin(string s)
    {
        string s1=s;
        reverse(s.begin(),s.end());
        if(s1.compare(s)==0)
            return true;
        return false;
    }
    string longestPalindrome(string s) {
       int n = s.length();
        if(n==1)
            return s;
       
        vector<vector<int>> dp(n,vector<int>(n,0));
        pair<int,int>coor;
        for(int i =0;i<n;i++)
        {
            dp[i][i]=1;
            coor=make_pair(i,i);
        }
        for(int i=0;i<n;i++)
        {
            int j=i+1;
            if(j<n)
            {
                if(ispalin(s.substr(i,j)))
                   {
                       dp[i][j]=1;
                       coor=make_pair(i,j);
                   }
                   else
                   {
                       dp[i][j]=0;
                   }
            }
        }
        for(int i=0;i<n;i++)
       {
            for(int j=2;j<n;j++)
            {
                if(i<j)
                {
                    if(s[i]==s[j] && dp[i+1][j-1]==1)
                    {
                        dp[i][j]=1;
                        coor=make_pair(i,j);
                    }
                    else
                        dp[i][j]=0;
                }
            }
       }
        return s.substr(coor.first,coor.second);
                   
    }

What I have tried to do is

  1. first for loop is to fill the diagonal elements.
  2. for loop is to fill elements for length 2 i.e - I check if that substring is palindrome if yes I make it 1 else 0.
  3. Whenever I update a cell to 1 I store coor pair to those coordinates so that they always have the latest values where 1 was updated.

It does not work on cases "bb", "ccc" how am I missing this case in the code?

Upvotes: 0

Views: 179

Answers (1)

another_CS_guy
another_CS_guy

Reputation: 682

The way you are using substr function is not correct. First argument should be the starting index and the second argument is the length of string.

Your code must be failing for this string as well "abccbdf".

Change

if(ispalin(s.substr(i,j)))

to this

if(ispalin(s.substr(i,2)))

And, in last return statement, your "coor" have correct value, but "substr" second argument is incorrect. Use this statement instead:

return s.substr(coor.first,coor.second-coor.first+1);

Upvotes: 1

Related Questions