目录
牛客_OR26最长回文子串
题目解析
C++代码1
C++代码2
Java代码
牛客_OR26最长回文子串
最长回文子串_牛客题霸_牛客网
描述：
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
题目解析
枚举所有的中心点，然后向两边扩散即可，也可用dp解决，回文串类型题目即解析：Offer必备算法21_回文串dp_六道力扣题详解（由易到难）-CSDN博客
C++代码1
dp解法代码：
class Solution {public:/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/int getLongestPalindrome(string A) {// dp[i][j]表示i位置为结尾，最外面的字符是j的回文串？// 暴力int sz = A.size();int ret = 1;for(int i = 0; i < sz; ++i){int len = 1; // 前面的防止越界不加也过了if(i != 0 && i != sz - 1 && A[i - 1] == A[i + 1]){int left = i - 1, right = i + 1;while(left >= 0 && right < sz && A[left--] == A[right++])len += 2;}// cout << len << endl;ret = max(ret, len);if(i != 0 && A[i - 1] == A[i]){len = 0;int left = i - 1, right = i;while(left >= 0 && right < sz && A[left--] == A[right++])len += 2;}ret = max(ret, len);if(i != sz - 1 && A[i] == A[i + 1]){len = 0;int left = i, right = i + 1;while(left >= 0 && right < sz && A[left--] == A[right++])len += 2;}ret = max(ret, len);}return ret;}
};C++代码2
中心拓展解法代码：
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;}
};Java代码
中心拓展解法代码：
import java.util.*;
public class Solution
{public int getLongestPalindrome (String s){// 中⼼扩展算法int n = s.length();int ret = 0;for(int i = 0; i < n; i++) // 枚举所有的中点{// 当⻓度为奇数的时候int left = i - 1, right = i + 1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}ret = Math.max(ret, right - left - 1);// 当⻓度为偶数的时候left = i; right = i + 1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}ret = Math.max(ret, right - left - 1);}return ret;}
}
