思路

题目分析

  1. 题目给出了我们一个字符串和字符串长度
  2. 我们需要在该字符串中找到一个最长的子字符串，这个字符串必须满足回文的特征。
  • 方法一：暴力中心拓展
    • 我们可以遍历这个字符串
    • 以每一个遍历到的字符作为中心，进行左右指针的拓展
    • 同时也要考虑到偶数长度的最长回文子字符串的情况
      • 这就要求我们必须将作为起点的字符先进行一个判断，是否右侧有相同的字符
      • 我们直接将右侧指针拉到和起点字符相同字符的最右侧，然后再进行双向拓展即可
  • 方法二：动态规划
    • 我们规定dp[l][r] == true表示从下标l到r的子字符串是回文串
    • 因此我们的动态规划数组递推满足以下逻辑
      • dp[l][l] == true 因为自身单字符必定是一个回文串
      • dp[l][l+1] == (A[i] == A[i+1]) 相邻的字符如果相同，则这两个构成回文子字符串
      • dp[l][r] == (A[l] == A[r] && dp[l+1][r-1]) 以l和r为界限的子字符串是否是回文串需要根据其更内一层是否是回文串来决定，同时要判断边缘两个是否也相同
    • 这样找到最长的一个即可

方法一：中心拓展

alt

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int mx = 0;
        for(int i = 0; i < n; i++) {
            int l = i;                                // 回文子串的左界限
            int r = i;                                // 回文子串的右界限
            while(r < n-1 && A[r]==A[r+1]) r++;       // 如果存在相同字符的连续子串，要直接将右侧界限拉到相同字符子串的最远端然后才进行两边拓展，主要是由于存在回文串为偶数长度的情况
            while(l >= 0 && r < n && A[l] == A[r]) {  // 进行回文两边界限拓展
                l--;
                r++;
            }
            mx = max(mx, r-l-1);                      // 不断更新最大值
        }
        return mx;
    }
};

复杂度分析

  • 时间复杂度：O(n2)O(n^2)，双重循环的时间代价
  • 空间复杂度：O(1)O(1)，只引入了常量级别空间代价

方法二：动态规划

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        bool dp[n][n];
        int mx = 0;
        for(int len = 0; len < n; len++) {                // 子串的长度
            for(int l = 0; l + len < n; l++) {            // 子串的起点
                int r = l + len;                          // 子串的终点
                if(len == 0)                              // 如果是单字符子串
                    dp[l][r] = true;                      // 则直接返回true
                else if(len == 1)                         // 如果是相邻的双字符子串
                    dp[l][r] = (A[l] == A[r]);            // 判断是否相同
                else 
                    dp[l][r] = (A[l] == A[r] && dp[l+1][r-1]);    // 其他情况就利用递推方程
                if(dp[l][r]) mx = max(mx, r-l+1);         // 统计最长串
            }
        }
        return mx;
    }
};

复杂度分析

  • 时间复杂度：O(n2)O(n^2)，双重循环的时间代价
  • 空间复杂度：O(n2)O(n^2)，dp空间的代价