leetcode题解-5.最长回文子串

文章目录

• 题目描述
• 思路解析
• 示例代码

博客专栏地址：https://blog.csdn.net/feng964497595/category_9848847.html

github地址：https://github.com/mufeng964497595/leetcode

题目描述

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

思路解析

1. 首先，题目是求子串，不是子序列，这个注意一下~

2. 这题目见过挺多次了，字符串长度是1000，常见方法就是用动态规划来处理：

   设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示字符串s的子区间 [ i , j ] [i, j] [i,j]是否是回文数，那么

   d p [ i ] [ j ] = { f a l s e , i > j t r u e , i == j d p [ i + 1 ] [ j − 1 ] , s[i] == s[j] && i+1 <= j-1 t r u e , s[i] == s[j] && i+1 > j-1 f a l s e , s[i]  ≠  s[j] dp[i][j] = \begin{cases} false, & \text{i > j} \\ true, & \text{i == j} \\ dp[i+1][j-1], & \text{s[i] == s[j] \&\& i+1 <= j-1} \\ true, & \text{s[i] == s[j] \&\& i+1 > j-1} \\ false, & \text{s[i] $\neq$ s[j]} \end{cases} dp[i][j]=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​false,true,dp[i+1][j−1],true,false,​i > ji == js[i] == s[j] && i+1 <= j-1s[i] == s[j] && i+1 > j-1s[i] ​= s[j]​

   这里解析一下上面这条公式：

• 当 i > j i>j i>j时，显然构不成字符串，直接置为false
• 当 i = = j i == j i==j时，字符串只有一个字符，肯定是回文串
• 当 s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]，且 i + 1 < = j − 1 i+1 <= j-1 i+1<=j−1时，区间 [ i + 1 , j − 1 ] [i+1, j-1] [i+1,j−1]是有效字符串，如果这个字符串是回文串，那么区间 [ i , j ] [i, j] [i,j]肯定也是；如果不是回文串，那区间 [ i , j ] [i, j] [i,j]也肯定不是，所以 d p [ i ] [ j ] = = d p [ i + 1 ] [ j − 1 ] dp[i][j] == dp[i+1][j-1] dp[i][j]==dp[i+1][j−1]
• 当 s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]，且 i + 1 > j − 1 i+1 > j-1 i+1>j−1时，即区间 [ i , j ] [i, j] [i,j]没有子串了，又因为区间 [ i , j ] [i, j] [i,j]最多只会有两个字符，且 s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]，所以区间 [ i , j ] [i, j] [i,j]是回文串
• 当 s [ i ] ≠ s [ j ] s[i] \neq s[j] s[i]​=s[j]，肯定就不会回文串

1. 当计算到 d p [ i ] [ j ] = t r u e dp[i][j] = true dp[i][j]=true时，更新此时的子串区间就可以了。为什么不用记录子串长度呢？因为题目没要求哈哈哈哈哈哈哈，而且计算dp的时候，区间 [ i , j ] [i, j] [i,j]长度是递增的，不会出现本次计算的回文串比上次计算出来的回文串短的情况，因此直接覆盖子串区间就好了。
2. 这里要注意一下边界情况：输入的字符串是空串时，直接返回空串即可。

示例代码

class Solution {
public:
    string longestPalindrome(const string& s) {
        if (s.empty())
            return s;

        // 初始化
        bool dp[1005][1005];
        memset(dp, 0, sizeof(dp));
        int len = s.length();
        for (int i = 0; i < len; ++i)
            dp[i][i] = true;

        int start = 0, end = 0;
        for (int step = 1; step < len; ++step) {
            for (int i = 0; i < len; ++i) {
                int j = i + step;
                if (j >= len) break;

                if (s[i] == s[j] && (i+1 >= j-1 || dp[i+1][j-1])) {
                    // [i+1, j-1]就是一个回文串，且s[i]==s[j]，则[i, j]也是一个回文串
                    dp[i][j] = true;
                    start = i;
                    end = j;
                }
            }
        }

        return s.substr(start, end - start + 1);
    }
};