即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 5. Longest Palindromic Substring 解题报告

编程语言 camellhf 13℃ 0评论
本文目录
[隐藏]

1.LeetCode 5. Longest Palindromic Substring 解题报告

1.1.题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.


1.2.示例

Example 1:


Input : “babad”


Output : “bab” (“aba” is also a valid answer)

Example 2:


Input : “cbbd”


Output : “bb”


1.3.注意事项

没有给出.


1.4.解题思路

1.4.1.动态规划解法:

如果用暴力破解的方法解决这道题,会发现在求解过程中做了很多重复的工作,因为对于每一个子串都需要重头到尾判断是不是回文的。

回文字符串具有一个性质:当去掉回文字符串的首尾字符后,剩下的子字符串仍然是回文的。反过来利用这个性质,如果我们已经知道了一个子字符串s[i + 1…..j – 1]是回文的,那么如果该字符串的前后字符相等,即s[i] == s[j],就可以直接判断s[i……j]是回文的。

因此可以用dp[i][j]表示s[i…j]是否回文,1表示是,0表示否。状态转移方程是


dp[i + 1][j – 1] == 1且s[i] == s[j],dp[i][j] = 1;


而初始条件有两种情况,分别是单个字符(a)跟两个相同字符(aa),所以初始化dp数组时需要对两种情况都进行初始化。

从状态转移方程可以看出,计算dp[i][j]时需要用到dp[i+1][j – 1]和dp[i + 1][j],所以对于i的遍历应该从尾部开始,见下面的动态规划实现。这种算法的时间复杂度跟空间复杂度都是O(n2)

1.4.2.Manacher算法:

下面讲解的Manacher算法是基于我自己的理解,所以可能会跟网络上其他资料有些出入,如果有错,欢迎评论指出。

Manacher算法分为以下几步:


1.为了解决奇偶长度回文字符串的不同,需要先对原来的字符串进行填充,得到填充字符串ps,比如abba,填充后成了#a#b#b#a#,为了避免越界的问题,在开头填充一个其他的字符,如$#a#b#b#a#,这样填充之后,奇偶长度的字符串都变成了偶数长度的字符串。

2.利用一个辅助数组p记录ps中最长回文字符子串的扩张长度,即p[i]表示以ps[i]为中心时的最大回文字符串向左右扩张的长度(包括s[i])。比如:


s[i] : $ # a # b # a #


p[i] : 1 1 2 1 4 1 2 1


观察后发现,p[i]的值为原始字符串以s[i]为中心时最长回文字符子串的长度-1,之所以是长度减一,是因为我的填充方式是填充成了偶数长度的字符串,网络上有些资料的填充方式是只在字符之间填充,填充结果是奇数长度。

3.既然p[i]的值能够计算出原始字符串的最长回文长度,问题就转为了怎样计算p[i]。


设置一个变量id表示回文子串的中心,变量mx表示以id为中心时回文子串的边界。


当需要计算p[i]时,i与mx有两种情况:


(1)i >= mx,即i在mx之外,只能以i为中心,左右元素逐对判断。


(2)i < mx,即i在mx之内,计算i关于id的对称点j,因为p[j]是已经计算好的,而回文具有对称的性质,所以利用p[j],我们可以得到关于p[i]的信息。此时又具有两种情况:


(2.1)p[j] < mx - i,表明以j为中心的回文子串是包含在以id为中心的回文子串中,根据回文的对称性可知以i为中心的回文子串也是包含在以id为中心的回文子串中,因此p[i] = p[j]。见下图:


2.1

(2.2)p[j] > mx – i, 表明以j为中心的回文子串部分包含在以id为中心的回文子串中,我们只能确保mx-i长度的部分是回文的(绿框部分),而超出mx的部分就只能逐对判断。见下图:


2.2

通过上述过程就能求得每一个p[i],由于题目是要返回回文子串,所以每次求完p[i]后都判断是否为当前最长的回文长度,是则保存回文的起始位置和长度,循环结束后截取相应的子串作为结果。


1.5.代码

1.5.1.动态规划:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length(), start = 0, maxLen = 1;
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
            if (i + 1 < n && s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                start = i;
                maxLen = 2;
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                if (dp[i + 1][j - 1] && s[i] == s[j]) {
                    dp[i][j] = 1;
                    if (j - i >= maxLen) {
                        start = i;
                        maxLen = j - i + 1;
                    }
                }
            }
        }

        return s.substr(start, maxLen);
    }
};

1.5.2.Manacher算法:

class Solution {
public:
    string longestPalindrome(string s) {
        // padding string
        string ps = "$#";
        for (char c : s) {
            ps += c;
            ps += '#';
        }
        ps += '\0';

        vector<int> p(ps.size());
        int id = 0, mx = 0;
        int start = 0, maxLen = 0;

        for (int i = 1; i < ps.size(); i++) {
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

            while (ps[i + p[i]] == ps[i - p[i]]) 
                p[i]++;

            if (i + p[i] > mx) {
                id = i;
                mx = i + p[i];
            }

            // record the longest Palindromic substring
            if (p[i] - 1 > maxLen) {
                start = (i - p[i]) / 2;
                maxLen = p[i] - 1;
            }
        }

        return s.substr(start, maxLen);
    }
};

1.6.总结

回文类的题目是动态规划蛮经典的问题,需要区分问的是回文序列还是回文子串,这周做的是回文字符串问题,主要是学习一下Manacher算法。


这个算法比较难理解的就是计算辅助数组的过程,其实就是利用了回文的对称性,结合图片演算几次就能有所体会,下一周还是会去做动态规划的题目(因为最不熟练就是动归(⊙﹏⊙)b),多练,把算法能力调高上去,努力加油~

转载请注明:CodingBlog » LeetCode 5. Longest Palindromic Substring 解题报告

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情