[leetcode 5]我的最长回文子串问题的解决方案真的找不到问题

Question

输入：

babad
abbd

输出：

ad
bb

预计：

bab
bb

代码：

#include<iostream>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlength=1;
        bool ispalindromic[1000][1000]={false};
        for(int i=0;i<s.length();i++)
            ispalindromic[i][i]=1;
                
        for(int l=2;l<s.length();l++){
            for(int i=0;i<s.length()-1; i++){
                int j=i+l-1;
                if(l==2&&s[i]==s[j]){
                    ispalindromic[i][j]=1;
                    maxlength=max(maxlength,j-i+1);
                    continue;}
                if(ispalindromic[i+1][j-1]&&s[i]==s[j]){
                    ispalindromic[i][j]=1;
                    maxlength=max(maxlength,j-i+1);
                }
            }}
        for(int i=0;i<s.length();i++){
        int j=i+maxlength-1;
            if(ispalindromic[i][j]){
                return s.substr(i,j);
            }
        }
        return s.substr(0,1);
    }
};

我首先创建了 ispalindromic[1000][1000] 并确保每个字母本身都是回文的。然后我从 2 的长度开始检查回文，依此类推。每当 ispalindromic 变为真时，代码就会更新 maxlength，这样最后代码就可以简单地使用 maxlength 来打印最长的回文。

Answer 1

此代码存在一些问题。

for 循环的索引当你考虑一个可能的子字符串的长度 l 时，你的 l 应该在 2 到 s.length() 之间，所以外部 for 循环应该是：

for(int l=2;l<=s.length();l++){你看我把l < s.length()改成了l <= s.length()
那么你的 i 内循环索引应该从 0 到 s.length()-l 当你考虑一个长度为 l。需要修改为：

for(int i=0;i<s.length()-l+1; i++){

那么if条件l=2应该修改为：

          if(l==2){
             if ( s[i] == s[j] ) {
              ispalindromic[i][j]=1;
               maxlength=max(maxlength,j-i+1);
             }

             continue;
         }

您需要将 s[i] == s[j] 移到 if 中，因为无论 s[i] == s[j] 是什么，您都需要按照您的代码继续。

您需要打印长度为 maxlength 的子字符串，因此您的 return 语句应为：return s.substr(i,maxlength);

经过这些更正，代码为：

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlength = 1;
        bool ispalindromic[1000][1000] = {false};

        for (int i = 0; i < s.length(); i++) {
            ispalindromic[i][i] = 1;
        }

        for (int l = 2; l <= s.length(); l++) {
            for (int i = 0; i < s.length() - l + 1; i++) {
                int j = i + l - 1;

                if (l == 2) {
                    if ( s[i] == s[j] ) {
                        ispalindromic[i][j] = 1;
                        maxlength = max(maxlength, j - i + 1);
                    }

                    continue;
                }

                if (ispalindromic[i + 1][j - 1] && s[i] == s[j]) {
                    ispalindromic[i][j] = 1;
                    maxlength = max(maxlength, j - i + 1);
                }
            }
        }

        for (int i = 0; i < s.length(); i++) {
            int j = i + maxlength - 1;

            if (ispalindromic[i][j]) {
                return s.substr(i, maxlength);
            }
        }

        return s.substr(0, 1);
    }
};

Answer 2

不确定您面临的问题。正确，解决了您的问题。

除此之外，这个也可以通过，和你的一样，也是动态规划的方法：

#include <cstdint>
#include <string>

const static struct Solution {
    using SizeType = std::uint_fast16_t;
    static std::string longestPalindrome(const std::string s) {
        const SizeType slen = std::size(s);

        if (slen < 2) {
            return s;
        }

        SizeType maxlen = 0;
        SizeType head = 0;
        SizeType curr = 0;

        while (curr < slen) {
            SizeType left = curr;
            SizeType right = curr;

            while (right < slen - 1 and s[right] == s[-~right]) {
                ++right;
            }

            curr = -~right;

            while (right < slen - 1 and left > 0 and s[-~right] == s[left - 1]) {
                ++right;
                --left;
            }

            SizeType templen = -~right - left;

            if (templen > maxlen) {
                head = left;
                maxlen = templen;
            }
        }

        return s.substr(head, maxlen);
    }
};


// -~x is simply x + 1;

参考资料

有关更多详细信息，请参阅 Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis^{1, 2}。

[leetcode 5]我的最长回文子串问题的解决方案真的找不到问题

[leetcode 5 ]Can't really find what's wrong in my solution for longest Palindrome substring problem

c++

algorithm

debugging

dynamic-programming

palindrome

参考资料