【LeetCode】5. Longest Palindromic Substring 最长回文子串

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
公众号：负雪明烛
本文关键词：最长回文子串，题解，leetcode, 力扣，python, C++, java

题目描述

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

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

题目大意

找出字符串中最长的回文子串。

解题方法

暴力遍历

遍历算法是我们最直观的解法，事实上也能通过OJ。我们使用的方法是两重循环确定子串的起始和结束位置，这样只要判断该子串是个回文，我们保留最长的回文即可。

代码很简单，C++版本如下：

class Solution {

public:

    string longestPalindrome(string s) {

        const int N = s.size();

        string res;

        for (int i = 0; i < N; i++) {

            for (int j = i; j < N; j++) {

                if (j - i + 1 >= res.size() && isPalindrome(s, i, j)) {

                    res = s.substr(i, j - i + 1);

                }

            }

        }

        return res;

    }

    // [start, end]

    bool isPalindrome(string& s, int start, int end) {

        const int N = s.size();

        int l = start, r = end;

        while (l <= r) {

            if (s[l++] != s[r--]) {

                return false;

            }

        }

        return true;

    }

};

动态规划

动态规划的两个特点：第一大问题拆解为小问题，第二重复利用之前的计算结果，来解答这道题。

那如何划分小问题呢，我们可以先把所有长度最短为1的子字符串计算出来，根据起始位置从左向右，这些必定是回文。然后计算所有长度为2的子字符串，再根据起始位置从左向右。到长度为3的时候，我们就可以利用上次的计算结果：如果中心对称的短字符串不是回文，那长字符串也不是，如果短字符串是回文，那就要看长字符串两头是否一样。这样，一直到长度最大的子字符串，我们就把整个字符串集穷举完了。

我们维护一个二维数组 dp，其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串。

当 i = j 时，只有一个字符，肯定是回文串；
如果 i = j + 1 ，说明是相邻字符，此时需要判断 s[i]是否等于 s[j] ；
如果 i 和 j 不相邻，即 i - j >= 2 时，除了判断 s[i] 和 s[j] 相等之外，dp[j + 1][i - 1] 若为真，就是回文串。

通过以上分析，可以写出递推式如下：

dp[i, j] = 1                                        if i == j

         = s[i] == s[j]                             if j = i + 1

         = s[i] == s[j] && dp[i + 1][j - 1]         if j > i + 1

Python 代码刚提交的时候超时了，但是使用set一下，看看是否只包含相同字符，这样就通过了！

class Solution(object):

    def longestPalindrome(self, s):

        """

        :type s: str

        :rtype: str

        """

        if len(set(s)) == 1: return s

        n = len(s)

        start, end, maxL = 0, 0, 0

        dp = [[0] * n for _ in range(n)]

        for i in range(n):

            for j in range(i):

                dp[j][i] = (s[j] == s[i]) & ((i - j < 2) | dp[j + 1][i - 1])

                if dp[j][i] and maxL < i - j + 1:

                    maxL = i - j + 1

                    start = j

                    end = i

            dp[i][i] = 1

        return s[start : end + 1]

C++版本代码如下，需要注意的是这里的res初始化为第一个字符：

class Solution {

public:

    string longestPalindrome(string s) {

        const int N = s.size();

        if (N == 0) return "";

        string res = s.substr(0, 1);

        vector<vector<bool>> dp(N, vector(N, false));

        // s[j, i]

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < i; j++) {

                dp[j][i] = (s[j] == s[i]) && (i == j + 1 || dp[j + 1][i - 1]);

                if (dp[j][i] && i - j + 1 >= res.size()) {

                    res = s.substr(j, i - j + 1);

                }

            }

            dp[i][i] = true;

        }

        return res;

    }

};

二刷—

马拉车算法。。待续

参考：
http://www.cnblogs.com/grandyang/p/4464476.html
https://segmentfault.com/a/1190000002991199

日期

2018 年 3 月 15 日 —— 雾霾消散，春光明媚
2019 年 1 月 19 日 —— 有好几天没有更新文章了

秒客网