文章目录

• 一. 题目信息
• • 1. 描述
  • 2. 示例
• 二. 解法
• • 1. 动态规划
  • • ①. 复杂度分析
    • ②. c++解法

一. 题目信息

1. 描述

给你一个字符串 s，找到 s 中最长的回文子串。
题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

2. 示例

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

示例 3：
输入：s = "ac"
输出："a"

二. 解法

1. 动态规划

算法思路：dp[ i ][ j ]的意思是 str.substr(i, j - i + 1) 是否为回文串，字符串从短到长进行遍历

①. 复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
• 空间复杂度：O(n^2)。

②. c++解法

class Solution {
public:
    string longestPalindrome(string s) {
        int slen = s.length();
        if (slen < 2) return s;
        int begin = 0, maxlen = 1; // 注意这里maxlen必须是1
        vector<vector<int>> dp(slen, vector<int>(slen));
        for (int i = 0; i < slen; i++) {
            dp[i][i] == 1;
        }
        // 从长度为2开始遍历
        for (int strlen = 2; strlen <= slen; strlen++) 
            for (int i = 0; i < slen; i++) {
                int j = i + strlen - 1;
                if (j >= slen) break;
                if (s[i] != s[j]) dp[i][j] = 0;
                else {
                    if (j - i < 3) dp[i][j] = 1; // 这里必须小于3
                    else dp[i][j] = dp[i+1][j-1];
                }
                if (dp[i][j] && j - i + 1 > maxlen) {
                    begin = i;
                    maxlen = j - i + 1;
                }
            }
        return s.substr(begin, maxlen);
    }
};