缺少边缘情况的最长回文子串

Question

这是我使用动态编程概念编写的代码。

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

我尝试做的是

第一个for循环是填充对角元素。
for 循环用于填充长度为 2 的元素，即 - 我检查该子字符串是否为回文，如果是，我将其设置为 1，否则为 0。
每当我将单元格更新为 1 时，我都会将 coor 对存储到这些坐标，以便它们始终具有更新 1 的最新值。

它不适用于“bb”、“ccc”案例，我怎么在代码中遗漏了这个案例？

Answer 1

您使用 substr 函数的方式不正确。第一个参数应该是起始索引，第二个参数是字符串的长度。

您的代码对于此字符串以及“abccbdf”一定是失败的。

改变

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

至此

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

并且，在最后一个 return 语句中，您的“coor”具有正确的值，但“substr”的第二个参数不正确。请改用此语句：

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

缺少边缘情况的最长回文子串

Longest palindromic substring missing an edge case

c++

algorithm

dynamic-programming

palindrome