当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.005.LongestPalindromicSubstring 最长回文子串

LeetCode.005.LongestPalindromicSubstring 最长回文子串

题目描述

005 Longest Palindromic Substring
https://leetcode-cn.com/problems/longest-palindromic-substring/

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

Example 1:

Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

解题过程

这道题面试被问过,不会做。
这次先自己绞尽脑汁想了想,一开始想着搞个滑动窗口O(n)遍历解决,发现行不通,回文子串的子串不一定回文。
只好看了看题解,中心扩展法 很好理解,自己实现了一下,O(n^2) 复杂度,很好写。 Manacher 马拉车算法是中心扩展法的升级,将复杂度降到了O(n),没仔细看。

中心扩展法O(n^2)

private static class SolutionV2020 {
    public String longestPalindrome(String s) {
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            // 以i为中心扩展
            String extend1 = extend(s, i, i);
            result = extend1.length() > result.length() ? extend1 : result;
            if (i + 1 < s.length()) {
                // 以 i,i+1 为中心扩展,应对长度为偶数的情况
                String extend2 = extend(s, i, i + 1);
                result = extend2.length() > result.length() ? extend2 : result;
            }
        }
        return result;
    }

    // 从 pivot1, pivot2 开始分别往左右扩展,返回最长的回文子串
    public String extend(String s, int pivot1, int pivot2) {
        while (pivot1 >= 0 && pivot2 < s.length() && s.charAt(pivot1) == s.charAt(pivot2)) {
            pivot1--;
            pivot2++;
        }
        return s.substring(pivot1+1, pivot2);
    }
}

动态规划O(n^2)

p[i,j] 表示子串 s[i,j] 是否回文串,若已知 s[i,j] 是否回文,则可轻松的知道左右各扩展一位的子串 s[i-1,j+1] 是否子串。
所以有递推公式:
p[i-1,j+1] = p[i,j] && s[i-1] == s[j+1] 或者写做
p[i][j] = p[i+1][j-1] && s[i] == s[j]
且有初始条件
p[i,i] = true
p[i,i+1] = s[i] == s[i+1]

填二维表的过程中,maxStr 记录当前得到的最长回文子串,每次得到一个 true 值时,比较是否比 maxStr 长度更长,如果是则更新 maxStr,填表结束后的 maxStr 就是最终结果。

观察我们要填的二维表格,由于 j > i,所以只需要用到 对角线右上方的半块表格,左下方的不需要。

  0 1 2 3 4
0 T
1   T
2     T
3       T
4         T

此外,由于 p[i][j] 依赖于 p[i+1][j-1] 的结果,也就是二维表格中 (i,j) 左下角 (i+1,j-1) 位置的值,所以我们要从左往右一列一列的竖着填表,才不会出现在计算 p[i][j] 的值时他依赖的中间结果还没计算的情况。

Manacher马拉车算法O(n)

暴力枚举所有子串O(n^3)


GitHub代码

algorithms/leetcode/leetcode/_005_LongestPalindromicSubstring/
https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_005_LongestPalindromicSubstring


上一篇 北京中医药大学第三医院看颈椎记录

下一篇 OpenResty

阅读
评论
667
阅读预计3分钟
创建日期 2019-11-22
修改日期 2020-05-21
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论