5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

解:这题我首先颠倒以下，用的最长公共子串的方法，发现有些情况下是错的，如aabfgbaa,这样求出来的回文串是错的

所以加一个判断条件，当颠倒后的字符下标加上当前连续字符串的长度，等于当前正序的字符时，再改变最长子串的长度

class Solution {
public:
    string longestPalindrome(string s) {
        int n =s.size();
        vector<vector<int>> vec(n+1,vector(n+1,0));
        int max_value=0;
        int start_pos=0;
        string s_rev=s;
        reverse(s_rev.begin(), s_rev.end());
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(s[i-1]==s_rev[j-1])
                {
                    vec[i][j]=vec[i-1][j-1]+1;
                    if(vec[i][j]>max_value)
                    {
                        //判断每个子回文串位置是否相等
                        int init_pos=n-(j-1)-1;
                        if(init_pos+vec[i][j]==i)
                        {
                            max_value=vec[i][j];
                            start_pos=i-max_value;
                        }
                    }
                }
            }
        }
        return s.substr(start_pos,max_value);
    }
};

中心扩散法和另外的动态规划尝试下

另外一个动态规划法

class Solution {
public:
    string longestPalindrome(string s) {
        int max_value=0;
        int start_pos=0;
        vector<vector<int>> vec(s.size(),vector<int>(s.size(),0));
        for(int len=1;len<=s.size();len++)
        {
            for(int i=0;i<s.size();i++)
            {
                int j=i+len-1;
                //下标已经越界，结束本次循环
                if(j>=s.size())
                {
                    break;
                }
                //如果为1个或两个字符时，不用判断内部
                //且长度为1和2的已排除 不会出现 i+1大于j-1的情况
                vec[i][j]=(len==1||len==2||vec[i+1][j-1])&&s[i]==s[j];
                if(vec[i][j]&&len>max_value)
                {
                        max_value=len;
                        start_pos=i;;
                }
            }
        }
        return s.substr(start_pos,max_value);
    }
};

原文链接: https://www.cnblogs.com/wangshaowei/p/12312872.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/391332

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

5. 最长回文子串

相关推荐