专栏首页程序猿杂货铺【LeetCode题解-005】Longest Palindrome Substring

【LeetCode题解-005】Longest Palindrome Substring

1题目

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"

原题地址:https://leetcode.com/problems/longest-palindromic-substring/

2翻译

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

3解法一

最长公共子串

我们自然的会想到 如下解法

反转 SS,使之变成 S'S′。找到 SS 和 S'S′ 之间最长的公共子串,这也必然是最长的回文子串。

但是这样的做法会有个问题:

Example 1:
s = 'caba', s1 = 'abac'
s s1 之间的最长公共子串为:'aba'
满足条件
Example 2:
s = 'abacdfgdcaba', s1 = 'abacdgfdcaba'
s s1 之间的最长公共子串为:'abacd'
但是这个字符串并不是回文字符串

我们可以看到,当 SS 的其他部分中存在非回文子串的反向副本时,最长公共子串法就会失败。为了纠正这一点,每当我们找到最长的公共子串的候选项时,都需要检查子串的索引是否与反向子串的原始索引相同。如果相同,那么我们尝试更新目前为止找到的最长回文子串;如果不是,我们就跳过这个候选项并继续寻找下一个候选。

这给我们提供了一个复杂度为 O(n^2)动态规划解法,它将占用 O(n^2)的空间(可以改进为使用 O(n)的空间)。

可以在地址 https://en.wikipedia.org/wiki/Longest_common_substring_problem 阅读更多关于最长公共子串的内容。

此处便不再赘述了!

4解法二

暴力法

选出所有子字符串可能的开始和结束位置,并检验它是不是回文。

  • 当字符串中字符出现次数为偶数时,必然可以加入最长回文子串
  • 当字符串中字符出现次数为奇数时,分情况讨论:
    • 如果出现次数为大于1的奇数n,则可以加入n-1个对应字符到最长回文子串,
    • 最终的最长回文子串,最中间还可以加入一个单一字符
    • 上面两条合并起来,即可以直接将出现最大奇数次数的字符都加入最长回文子串
    • 即if(出现奇数次数的字符数==0),return s.length()
    • if(出现奇数次数的字符数!=0),return s.length()- 出现奇数次数的字符数+1

5解法三

动态规划

为了改进暴力法,我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 ' ababa' 这个示例。如果我们已经知道 'bab' 是回文,那么很明显,'ababa' 一定是回文,因为它的左首字母和右尾字母是相同的。

我们给出 P(i,j)P(i,j) 的定义如下:

这产生了一个直观的动态规划解法,我们首先初始化一字母和二字母的回文,然后找到所有三字母回文,并依此类推…

/**
     * 动态规划算法
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int maxLength = 0;
        String longest = null;

        int length = s.length();
        boolean[][] table = new boolean[length][length];

        // 单个字符都是回文
        for (int i = 0; i < length; i++) {
            table[i][i] = true;
            longest = s.substring(i, i + 1);
            maxLength = 1;
        }

        // 判断两个字符是否是回文
        for (int i = 0; i < length - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                table[i][i + 1] = true;
                longest = s.substring(i, i + 2);
                maxLength = 2;
            }
        }


        // 求长度大于2的子串是否是回文串
        for (int len = 3; len <= length; len++) {
            for (int i = 0, j; (j = i + len - 1) <= length - 1; i++) {
                if (s.charAt(i) == s.charAt(j)) {
                    table[i][j] = table[i + 1][j - 1];
                    if (table[i][j] && maxLength < len) {
                        longest = s.substring(i, j + 1);
                        maxLength = len;
                    }
                } else {
                    table[i][j] = false;
                }
            }
        }
        return longest;
    }

6解法四

中心扩展算法

事实上,只需使用恒定的空间,我们就可以在 O(n^2) 的时间内解决这个问题。这也是官网的一种经典解法

我们观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,并且只有 2n - 1个这样的中心。

你可能会问,为什么会是 2n - 12n−1 个,而不是 nn 个中心?原因在于所含字母数为偶数的回文的中心可以处于两字母之间(例如 'abba'的中心在两个 'b' 之间)。

/**
     * 中心扩展算法
     * 回文中心的两侧互为镜像。因此,回文可以从它的中心展开,并且只有 2n - 12n−1 个这样的中心。
     * 时间复杂度:由于围绕中心来扩展回文会耗去 O(n)O(n) 的时间O(n^2)
     * 空间复杂度:O(1)
     *
     * @param s
     * @return
     */
    public static String longestPalindrome2(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        // 当回文串的长度为奇数时
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

7Manacher算法

这是LeetCode官网上的一种复杂度只到 O(n)的解法,可以说是屌炸天了,膜拜中... ...

如果你感兴趣的话可以了解一下,地址在这里:https://articles.leetcode.com/longest-palindromic-substring-part-ii/

题外话:由于本人最近工作比较忙,所以刷题数量可能会稍微降低一点,但是会保证一周最少3-4题,共勉!

以上代码会同步更新在本人的Github和CSDN上

Github地址:https://github.com/Bylant/LeetCode

本文分享自微信公众号 - 程序猿杂货铺(zhoudl_l),作者:zhoudl

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode题解-009】Palindrome Number

    Determine whether an integer is a palindrome. An integer is a palindrome when it...

    周三不加班
  • 【算法】几道常见的算法字符串算法题

    谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把字符匹配的时间复...

    周三不加班
  • MYSQL 数据库时间字段 INT,TIMESTAMP,DATETIME 性能效率比较

    在数据库设计的时候,我们经常会需要设计时间字段,在 MYSQL 中,时间字段可以使用 int、timestamp、datetime 三种类型来存储,那么这三种类...

    周三不加班
  • PAT1040 Longest Symmetric String (25分) 中心扩展法+动态规划

    Given a string, you are supposed to output the length of the longest symmetric s...

    vivi
  • LeetCode攀登之旅(5)

    Given a string s, find the longest palindromic substring in s. You may assume th...

    公众号guangcity
  • POJ 3026 Borg Maze(BFS+Kruskal)(傻逼题)

           这道题不是一般的坑,先说一下思路,我们对于每一个A和S跑一遍BFS,用来求当前点到所有A和S的最短距离当两点间的权值存起来,然后再跑一遍最小生成树...

    Ch_Zaqdt
  • 在64位系统下,指向int型的指针占的内存空间多大?

    黑泽君
  • leetcode Problem 5 最长子回文串

    1、暴力做法。 遍历所有的子串,求出最长。复杂度O(n3)。显然GG了。 2、动态规划 把一个大问题分解成每一个小问题进行求解。假设字符串s,则s[...

    flytam
  • Leetcode#832. Flipping an Image(翻转图像)

    水平翻转图片就是将图片的每一行都进行翻转,即逆序。例如,水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

    武培轩
  • LeetCode 276. 栅栏涂色(DP)

    有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏,每个栅栏柱可以用其中一种颜色进行上色。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券