[M枚举] lc5. 最长回文子串(枚举+中心拓展+区间dp)「建议收藏」

[M枚举] lc5. 最长回文子串(枚举+中心拓展+区间dp)「建议收藏」文章目录1.题目来源2.题目解析方法一:枚举1.题目来源链接:lc5.最长回文子串2.题目解析方法一:枚举回文串一共有两种,即长度为奇数的回文串,长度为偶数的回文串。我们可以枚举回文串的中心(偶数长度回文串假想一个中心就行了),然后分别拿两个指针l=i-1,r=i+1向左右两边同时拓展,若s[l]=s[r]则,l–,r++。一直进行该操作,直到不等或一方到达边界位置。我们针对每一个枚举位置i,都考虑其两种情况,即偶数,奇数都考虑一遍,取个最大的就行了。

大家好,又见面了,我是你们的朋友全栈君。

1. 题目来源

链接:lc5. 最长回文子串

2. 题目解析

方法一:枚举

回文串一共有两种,即长度为奇数的回文串,长度为偶数的回文串。我们可以枚举回文串的中心(偶数长度回文串假想一个中心就行了),然后分别拿两个指针 l = i - 1r = i + 1 向左右两边同时拓展,若 s[l]=s[r] 则,l --, r ++。一直进行该操作,直到不等或一方到达边界位置。

我们针对每一个枚举位置 i,都考虑其两种情况,即偶数,奇数都考虑一遍,取个最大的就行了。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

至于本问题,还有一些非常秀的方法。dp 在这也只能达到 O ( n 2 ) O(n^2) O(n2) 的时间复杂度,且还要开辟 dp 数组。

其中,字符串哈希+二分,貌似能够做到 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度。

至于那个,马拉车算法,之前简单看过,专门解决最长回文子串问题,时间复杂度能达到 O ( n ) O(n) O(n),不过可拓展性非常之低。

本题采用的中心拓展思想在别的问题中也能用到~

代码:

// 暴力直接算,即中心扩散,时间复杂度为O(n^2) 字符串最好能在1000以内的长度
// 动规可以算,时间复杂度为O(n^2) 
// 马拉车算法,专门解决最长回文子串问题,时间复杂度能达到O(n)

class Solution { 
   
public:
    string longestPalindrome(string s) { 
   
        int n = s.size();
        string res;
        for (int i = 0; i < n; i ++ ) { 
   
            // 处理回文串长度为奇数的情况
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);   // 左闭右开区间

            // 处理回文串为偶数的情况
            l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
        }
        return res;
    }
};

方法二:区间 dp

更新于 2021 年 4 月 16 日晚。字符串区间 dp 的题目比较少,经典有 lc 87 题,dfs 超时,区间 dp 可解,lc 87 是很难的一道题。

官方题解思路蛮不错的,三种方法都有涉及。

思路:

  • f[i][j] 表示 s[i : j] 能否构成回文串。
  • 当区间长度为 1 时,必然构成一个回文串,即 f[i][i] = true;
  • 字符串区间 dp 最重要的就是 枚举长度,要理解这个枚举顺序。
  • 枚举长度,再枚举左边界,通过长度确定右边界坐标。
  • 若右坐标合法,那么判断左右坐标对应字符是否相等,若不等则 f[i][j] 不构成回文串。否则,如果区间长度小于 3 的话,那么就直接是 f[i][j]=true,因为只有两个数字的话,f[i+1][j-1] 直接交换位置…造成状态的错误更新。否则区间长度大于等于三时,s[i : j] 首先两侧字符相等,那么 f[i][j] = f[i+1][j-1]。这两者是等价的。进行状态转移即可。

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n 2 ) O(n^2) O(n2)


很经典的一道题目,三种解法中的任一种都是非常经典且值得学习的。中心拓展、区间 dp 都是非常常用的思想,而马拉车不常用,但它却是能 O ( n ) O(n) O(n) 的解决该问题!日后再补吧,以前总结了,又忘了…

class Solution { 
   
public:
    string longestPalindrome(string s) { 
   
        int n = s.size();
        if (n < 2) return s;

        // f[i][j] 表示 s[i:j] 这一段是回文串,区间 dp
        vector<vector<bool>> f(n, vector<bool>(n));

        // 长度为 1 的串必然是回文的
        for (int i = 0; i < n; i ++ ) f[i][i] = true;

        // 最短的回文串长度就是 1,在这初始化 mx=0 的话会出错
        // 可能整个串中都没有长度大于 2 的回文串,那么最后 substr() 的时候就会出错了,如 "ac"
        int mx = 1, l = 0;      
        for (int len = 2; len <= n; len ++ ) { 
         // 枚举子串长度
            for (int i = 0; i < n; i ++ ) { 
            // 枚举左边界。根据长度得到右边界下标
                int j = len + i - 1;                // [i, j] 有 j-i+1 个数
                if (j >= n) break;                  // 右边界越界,左区间不需要再向右了,退出当前循环

                if (s[i] != s[j]) f[i][j] = false;  // [i,j] 不构成回文串
                else { 
   
                	// 等价 if (len < 3) 因为只有两个数字的话,f[i+1][j-1] 直接交换位置...
                    if (j - i < 3) f[i][j] = true;  // [i,j] 长度小于等于 2 只要s[i]==s[j]就构成回文串
                    else f[i][j] = f[i + 1][j - 1]; // 可能构成回文串,取决于 s[i+1:j-1] 是否能构成回文串
                }
                if (f[i][j] && j - i + 1 > mx) { 
   
                    mx = j - i + 1;
                    l = i;
                }
            }
        }
        return s.substr(l, mx);
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164020.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号