NC 最长回文子串

系列文章目录

---

---

前言

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。

---

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

解题思路：
维护一个布尔型的二维数组dp，dp[i][j]表示 i 到 j 的子串是否是回文子串

每次先判断边界字符是否相等，再取决于上个状态的判断结果

算法流程：
维护一个布尔型的二维数组dp，dp[i][j]表示 i 到 j 的子串是否是回文子串
从长度0到字符串长度n进行判断
选定起始下标 i 和终止下标 j， i 和 j 分别为要比较的字符串的左右边界指针
从左右边界字符开始判断，即 A.charAt(i) == A.charAt(j)
当相等时，还要判断当前长度 c 是否大于1，不大于则表明只有两个字符的字符串，一个或两个字符肯定是回文串，如“11”
判断的长度大于1时，因为最左右的字符已经相等，因此取决于上一次的子串是否是回文子串, 如 “12121”
更新回文串的最大长度
Java 版本代码如下：

import java.util.*;
public class Solution {public int getLongestPalindrome(String A, int n) {// 动态规划：i到j的子串是否是回文子串boolean[][] dp = new boolean[n][n];int max = 0;// 字符串长度差 c = j-i，即当前要比较的字符串长度，这里可以 c <= n / 2 + 1，减少判断次数for(int c = 0; c <= n + 1; c++) {// 起始下标，范围取决于要判断的字符串长度c// i 和 j 分别为要比较的字符串的左右边界指针for(int i = 0; i < n - c; i++) {// 终点下标int j = c + i;// 左右边界的字符相等if(A.charAt(i) == A.charAt(j)) {// c <= 1表示只有两个字符的字符串，一个或两个字符肯定是回文串if(c <= 1) {dp[i][j] = true;} else {// 对于两个字符以上的字符串// 因为最左右的字符已经相等，因此取决于内层的子串是否是回文子串dp[i][j] = dp[i + 1][j - 1];}// 更新回文串的最大长度，c代表判断的子串长度，越来越大if(dp[i][j]) {max = c + 1;}}}}return max;}
}

复杂度分析：
时间复杂度 O(N^2)：N为字符串长度，平均判断的子串长度从0到N
空间复杂度 O(N^2)：需要维护二维数组，代表转移方程的状态