题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ /** 思路:创建boolean 类型 二维dp[i][j] 表示从i到j是否是回文子串 从子串长度入手0 ~ n-1 然后遍历每一个起始 i 判断当前 i到j是否是回文子串 如果 子串长度为0 或者 1 则一定是 如果 子串长度 >1 则要判断 当前子串的子串dp[i+1][j-1] 是否是回文子串 */ public int getLongestPalindrome (String A) { // write code here int res = -1; int n = A.length(); //dp[i][j] 表示从i到j 这个子串是否是回文串 boolean [][]dp = new boolean[n][n]; //子串长度 从1开始遍历到整个字符串的长度 for (int c = 0 ; c < n ; c++) { for (int i = 0 ; i < n - c ; i++) { // i 是子串开始的下标 // j 是子串结束的下标 int j = i + c; if (A.charAt(i) == A.charAt(j)) { //当当前子串长度为 0 或 1 时 代表只有一个字符 一定是回文串 if (c <= 1) { dp[i][j] = true; } else { if (dp[i + 1][j - 1]) dp[i][j] = true; } if(dp[i][j]) res = Math.max(res,c + 1); } } } return res; } }