005 最长回文子串

题目

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

示例 1

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2

输入: "cbbd"
输出: "bb"

示例 3

输入: "a"
输出: "a"

实现

回文是一个正读和反读都相同的字符串,例如,“aba”是回文,而“abc”不是。

第一种:暴力法,列举所有的子串,判断该子串是否为回文

  • 执行结果:超出时间限制
public class Solution
{
    public string LongestPalindrome(string s)
    {
        if (string.IsNullOrEmpty(s))
            return string.Empty;
        if (s.Length == 1)
            return s;

        int start = 0;
        int end = 0;
        int len = int.MinValue;
        for (int i = 0; i < s.Length; i++)
        {
            for (int j = i + 1; j < s.Length; j++)
            {
                string str = s.Substring(i, j - i + 1);
                if (isPalindrome(str) && str.Length > len)
                {
                    len = str.Length;
                    start = i;
                    end = j;
                }
            }
        }
        return s.Substring(start, end - start + 1);
    }

    public bool isPalindrome(string s)
    {
        for (int i = 0, len = s.Length / 2; i < len; i++)
        {
            if (s[i] != s[s.Length - 1 - i])
                return false;
        }
        return true;
    }
}

第二种:动态规划

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。

我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

具体的动态规划算法多种多样,但它们具有相同的填表格式。

使用记号 s[l, r] 表示原始字符串的一个子串,lr 分别是区间的左右边界的索引值,使用左闭、右闭区间表示左右边界可以取到。

dp[l, r] 表示子串 s[l, r](包括区间左右端点)是否构成回文串,是一个二维布尔型数组。

  • 当子串只包含 1 个字符,它一定是回文子串;
  • 当子串包含 2 个以上字符的时候:s[l, r] 是一个回文串,那么这个回文串两边各往里面收缩一个字符(如果可以的话)的子串 s[l + 1, r - 1] 也一定是回文串。

故,当 s[l] == s[r] 成立的时候,dp[l, r]的值由 dp[l + 1, r - l] 决定,这里还需要再多考虑一点点:“原字符串去掉左右边界”的子串的边界情况。

  • 当原字符串的元素个数为 3 的时候,如果左右边界相等,那么去掉它们以后,只剩下 1 个字符,它一定是回文串,故原字符串也一定是回文串;
  • 当原字符串的元素个数为 2 的时候,如果左右边界相等,那么去掉它们以后,只剩下 0 个字符,显然原字符串也一定是回文串。

综上,如果一个字符串的左右边界相等,判断为回文只需以下二者之一成立即可:

  • 去掉左右边界以后的字符串不构成区间,即s[l + 1, r - 1]包含元素少于2个,即:r - l <= 2
  • 去掉左右边界以后的字符串是回文串,即dp[l + 1, r - 1] == true

C# 实现

  • 状态:通过
  • 103 / 103 个通过测试用例
  • 执行用时: 232 ms, 在所有 C# 提交中击败了 46.79% 的用户
  • 内存消耗: 40.9 MB, 在所有 C# 提交中击败了 5.43% 的用户
public class Solution {
    public string LongestPalindrome(string s) 
    {
        if (string.IsNullOrEmpty(s))
            return string.Empty;
        int len = s.Length;
        if (len == 1)
            return s;
        int longestPalindromelen = 1;
        string longestPalindromeStr = s.Substring(0, 1);
        bool[,] dp = new bool[len, len];

        for (int r = 1; r < len; r++)
        {
            for (int l = 0; l < r; l++)
            {
                if (s[r] == s[l] && (r - l <= 2 || dp[l + 1, r - 1] == true))
                {
                    dp[l, r] = true;
                    if (longestPalindromelen < r - l + 1)
                    {
                        longestPalindromelen = r - l + 1;
                        longestPalindromeStr = s.Substring(l, r - l + 1);
                    }
                }
            }
        }
        return longestPalindromeStr;        
    }
}

Python 实现

  • 执行结果:通过
  • 执行用时:3392 ms, 在所有 Python3 提交中击败了 43.87% 的用户
  • 内存消耗:21.2 MB, 在所有 Python3 提交中击败了 18.81% 的用户
class Solution:
    def longestPalindrome(self, s: str) -> str:
        count = len(s)
        if count == 0 or count == 1:
            return s
        longestPalindromelen = 1
        longestPalindromeStr = s[0:1]
        dp = [[False] * count for i in range(count)]
        for r in range(1, count):
            for l in range(0, r):
                if s[r] == s[l] and (r - l <= 2 or dp[l + 1][r - 1] == True):
                    dp[l][r] = True
                    if longestPalindromelen < r - l + 1:
                        longestPalindromelen = r - l + 1
                        longestPalindromeStr = s[l:l + longestPalindromelen]
        return longestPalindromeStr

参考文献

浙ICP备19012682号