当前位置 博文首页 > 文章内容

    中等-5-最长回文子串

    作者: 栏目:未分类 时间:2020-08-07 18:00:38

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    LeetCode5

    给定一个字符串 s,找到 s 中最长的回文子串。

     

    一、暴力解法

    最暴力的解法是判断s的每个子串是否为回文串,复杂度为立方级,在此不做实现。

    这里实现的是中心扩散的思想,即利用回文串中心对称的性质,遍历s的每个字符,其作为回文串的中心,依次向两边扩展更新当前回文串,若超过res则更新res。

    复杂度为O(n2)。

    以下代码花了几分钟写的,未优化。

    class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            String res = "";
            if(len==0) return res;
            int resLen = 0;
         // 奇回文子串
    for(int i=0; i<len; i++){ int cur = 1; int left = i-1; int right = i+1; while(left>=0&&right<=len-1&&s.charAt(left)==s.charAt(right)){ left--; right++; cur += 2; } if(cur>resLen){ resLen = cur; res = s.substring(++left,right); } }
         // 偶回文子串
    for(double i=0.5; i<=len-1.5; i++){ int cur = 0; int left = (int) (i-0.5); int right = (int) (i+0.5); while(left>=0&&right<=len-1&&s.charAt(left)==s.charAt(right)){ left--; right++; cur += 2; } if(cur>resLen){ resLen = cur; res = s.substring(++left,right); } } return res; } }

     

     

    二、动态规划

    dp[i][j] 表示 s[i,j](两边闭)是否为回文串。   状态转移方程: dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]。

    初始化二维数组对角线为true,并只需维护该对角线以上部分,注意临界范围为 j-i<3 。若该区间为true且长度大于res,则更新目标值。

    class Solution {
        public String longestPalindrome(String s) {
            int len = s.length();
            if(len < 2) return s;
            int resLen = 1;
            int begin = 0;
            boolean[][] dp = new boolean[len][len];
            for(int i=0; i<len; i++)
                dp[i][i] = true;
            for(int j=1; j<len; j++){
                for(int i=0; i<j; i++){
                    if(s.charAt(i)!=s.charAt(j)){
                        dp[i][j] = false;
                    } else {
                        if(j - i < 3)
                            dp[i][j] = true;
                        else dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j] && j - i + 1 > resLen){
                        resLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin,begin + resLen);
        }
    }

     

     

    三、