IT虾米网

最长回文子串算法详解

shasha 2020年11月01日 编程语言 189 0

给定一个字符串 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); 
    } 
};

 

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

每日温度算法详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。