题解 | #密码截取#

题目链接https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1?tpId=37&&tqId=21255&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37

题目描述

求一个串的最长回文子串？

方法一：中心对称向外扩展

• 不难发现，回文串只存在两种形式:
  • 1.AA型:即由偶数个字符组成的回文串
  • 2.ABA型:即由奇数个字符组成的回文串
  所以我们只需遍历每一个数时判断以当前数为中心向外扩展构成的AA型与ABA型回文串的最大长度即可算法执行过程如图(以样例12HHHHA举例)： i表示当前遍历的元素，假设某一时刻i遍历到途中元素时
• 先计算能扩展的最长AA型的长度，扩展方式即以i为中心，分别向i的左右向外直至碰到左右两边出现不相等的情况。
• 再计算能扩展的最长ABA型的长度,扩展方式即以i和i + 1为中心，分别向i与i + 1的左右向外直至碰到左右两边出现不相等的情况。注意：ABA型只有i和i + 1代表的元素相等才可能构成回文串，否则不必扩展。
• 按这种方式计算，每个元素为中心的两种回文情况都能考虑到，故一定能求得最终解。

时间复杂度:需要遍历一遍数组，然后对每个元素执行两次向外扩展，故为O(n²)

空间复杂度：O(1)

参考代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 3e3 + 10;

int main()
{
   string a;
   cin >> a;
   int ans = 1;
   /*遍历每一个元素*/
   for (int i = 0; i < a.size(); i ++ ) {
       /*扩展计算最长AA型的回文串*/
   	int l = i - 1, r = i + 1;
   	while (l >= 0 && r < a.size() && a[l] == a[r]) {
   		ans = max(ans, r - l + 1);    //更新答案
   		l -- , r ++ ;
   	}
       /*扩展计算最长ABA型的回文串*/
   	l = i, r = i + 1;
   	while (l >= 0 && r < a.size() && a[l] == a[r]) {
   		ans = max(ans, r - l + 1);    //更新答案
   		l -- , r ++ ;
   	}
   }	
   cout << ans << "\n";
   return 0;
}

方法二：动态规划

dp[j][i]表示索引j到索引i的子串是否是回文串,可以发现有如下三种情况可以转移：

• 1.i == j: 此时只有一个元素，是回文串，故dp[i][j] = true;
• 2.i - j = 1 && str[i] == str[j]: 此时回文，dp[i][j] = true;
• 3.i - j > 1 && str[i] == str[j] && dp[i - 1][j + 1]: dp[i][j] = true;

代码如下

#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int N = 3e3 + 10;
int dp[N][N];

int main(){
    string s;
    cin >> s;
    int n = s.size();
    int maxn = 1;       //最长回文子串的长度初始化为1
    for (int i = 0; i < n; i++ )
        for (int j = 0; j <= i; j++ )
        {
            /*状态转移*/
            if(i == j) dp[j][i] = 1;
            else if (i-j == 1) dp[j][i] = (s[i]==s[j]);
            else dp[j][i] = ( s[j] == s[i] && dp[j+1][i-1] );
            if(dp[j][i] && maxn < i - j + 1) maxn = i - j + 1;  //更新答案
        }
    cout << maxn << endl;
    return 0;
}

时间复杂度: O(n²)

空间复杂度: O(n²)