题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ public int getLongestPalindrome (String A) { // write code here //定义dp数组,由于回文串结构,一个字符串可以由dp[i+1][j-1]来推dp[i][j]是否是回文串 //子问题就是往里缩 int len = A.length(); boolean dp[][] = new boolean[len][len]; int max = 1; //从dp[i+1][j-1]来推dp[i][j]可以得出,这个需要从左下往右上进行遍历 for (int i = len - 1; i >= 0; i--) { //j要大于等于i [i,j] for (int j = i; j < len; j++) { if (A.charAt(i) == A.charAt(j)) { if (j - i <= 1) { //a/aa dp[i][j] = true; max = Math.max(j - i + 1, max); } else if (j - i > 1) { if (dp[i + 1][j - 1]) { dp[i][j] = true; max = Math.max(j - i + 1, max); } } } } } return max; } }