笔试训练48天：最长回文子串

REAL473 最长回文子串

知识点字符串动态规划

描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围： 1≤n≤10001≤n≤1000

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n2)O(n2)

进阶: 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入："ababc" 返回值：3

说明：最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入："abbba" 返回值：5

示例3

输入："b" 返回值：1

知识点：子串：数组中连续的部分

算法原理：

1.动态规划 时间复杂度：n^2,空间复杂度:n^2

2.马拉车算法:时间复杂度：n,空间复杂度:n

3.中心扩展算法:时间复杂度：n^2,空间复杂度:1

中心扩展算法:1.枚举中心位置的时候要考虑回文子串长度的奇偶性

2.如何计算长度(right-left-1)

#include <algorithm> #include <iostream> using namespace std; class Solution { public: int getLongestPalindrome(string s) { int ret=1,n=s.size(); for(int i=1;i<n;i++) { //当长度是奇数时 int left=i-1,right=i+1; while (left>=0&&right<n&&s[left]==s[right]) { left--;right++; } ret=max(ret, right-left-1); //当长度为偶数时 left=i-1,right=i; while (left>=0&&right<n&&s[left]==s[right]) { left--;right++; } ret=max(ret, right-left-1); } return ret; } };