vlambda博客
学习文章列表

你必须掌握动态规划——LeetCode题目5:最长回文子串

原题描述



+



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

示例 1

输入:"babad"

输出:"bab"

注意: "aba" 也是一个有效答案。

示例 2

输入:"cbbd"

输出:"bb"

原题链接:https://leetcode-cn.com/problems/longest-palindromic-substring

思路解析



+


这道题有多种解法,但我只想谈谈我认为面试中比较重要,并且常考的解题方法——动态规划


如果不了解动态规划方法的,我在这里简单的介绍下。凡是符合动态规划类型的题目都具有以下两个重要特征,大家务必烂熟于心:

1. 重叠子问题:即原问题和子问题只有规模的不同,原问题可以分解为若干结构规模较小的子问题,可以建立原问题与子问题之间的递推关系。

2. 最优子结构:原问题的最优解一定是在子问题的最优解之上。


可能还是有点虚,那我们一边做题一边了解吧~


假设   表示从   到   的子串是否是回文,   表示字符串   中第   个字符,那么原问题与子问题的关系为:

   

但是这个递推分解总会到最原子的问题规模。对于这道题来说,最原子的问题是一个字符和两个字符的情况:一个字符本身可以看做回文,两个字符只要相等也是回文,于是有:

 

 

好了,看到这里,这道题你已经解决了可以直接把上面的递推公式写成递归编写程,但是动态规划的精髓在于缓存子问题的结果。


动态规划的解题方法是:把上面的   看成是二维矩阵,递推公式表明了矩阵上当前位置的元素和其他位置元素的关系,如此不断递推下去补充矩阵,问题迎刃而解。


那么你可能已经感觉到,动态规划最难的点就是在于寻找递推关系,我们称之为动态方程,而题目中使用的矩阵成为动态规划矩阵。


复杂度分析



+


  • 时间复杂度:   

  • 空间复杂度:   

计算步骤



+


1. 在矩阵中填写最原子问题——只有一个字符的情况,记录length为1,并且任意位置都可以作为起始位置。

2. 在矩阵中填写另一个原子问题——只有两个字符的情况,记录最长的length,并记录字符串起始位置。

3. 开始根据递推关系补充矩阵,直到结束,一边填充矩阵一边记录起始位置和最长长度。


C++参考代码



+



class Solution {
public:
    string longestPalindrome(string s) {
        int length = s.size();
        int start = 0, palind_len = 0;
        vector<vector<bool>> dp(length, vector<bool>(length, false));
        for (int i = 0; i < length; ++i) {
            dp[i][i] = true;
            start = i;
            palind_len = 1;
        }
        for (int i = 0; i < length - 1; ++i) {
            if (s[i] == s[i+1]) {
                dp[i][i+1] = true;
                start = i;
                palind_len = 2;
            }
        }
        for (int stride = 2; stride < length; ++stride) {
            for (int i = 0; i + stride < length; ++i) {
                if (s[i] == s[i+stride] && dp[i+1][i+stride-1]) {
                    dp[i][i+stride] = true;
                    if (palind_len < stride + 1) {
                        start = i;
                        palind_len = stride + 1;
                    }
                }
            }
        }
        return s.substr(start, palind_len);
    }
};


讲技术,也谈风月,更关注程序员的生活状况,欢迎联系二少投稿你感兴趣的话题。