最长回文串

问题描述

给你一个字符串 s，找到 s 中最长的回文子串。

问题分析

策略选择

算法设计

  1. 问题分解划分阶段：规模增长的方向有两个，第一个是最长回文串的长度，第二个是字符串的长度。
  2. 确定状态变量dp[i][j]。表示长度为i，以j为起点的字符串是否是回文串。
  3. 确定状态转移方程。长度减2，起始位置为j+1的回文字符串。
    $$
    dp[i][j]=dp[i-2][j+1] and s[j]==s[j+1-1]
    $$
  4. 确定边界实现过程。i增长的边界是n，表示最大长度为n，i=0,和i=1时，值都初始化为1；j增长的边界是0到n-i

算法分析

  • 时间复杂度O(n^2)
  • 空间复杂度O(n^2)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
// 思路1 动态规划
    string longestPalindrome(string s) {
        int n=s.size();
        if(n==0)return "";
        if(n==1)return s;
        vector<vector<int>> vec(n+1,vector<int>(n,0));
        for(int i=0;i<n;i++){
            vec[0][i]=1;
            vec[1][i]=1;
        }
        // length
        int max=1;
        string result=s.substr(0,1);
        for(int i=2;i<=n;i++){
            for(int j=0;j<=n-i;j++){
                if(s[j]==s[j+i-1] && vec[i-2][j+1]){
                    vec[i][j]=1;
                    if(i>max){
                        max=i;
                        result = s.substr(j,i);
                    }
                }
            }
        }
        return result;
    }
};