牛客题解-NC17最长回文子串

发表于 更新于 分类于 阅读次数：

题目

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

示例1

输入：

1
"abc1234321ab",12

输出：

1
7

思路

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for(int l = 0; l < n; l++){
            for(int i = 0; i + l < n; ++i){
                int j = i + l;
                if(l == 0){
                    dp[i][j] = true;
                }else if(l == 1){
                    dp[i][j] = (A.charAt(i) == A.charAt(j));
                }else{
                    dp[i][j] = (dp[i+1][j-1] && A.charAt(i) == A.charAt(j));
                }
                if(dp[i][j] && l + 1 > ans.length()){
                    ans = A.substring(i,i+l+1);
                }
            }
        }
        return ans.length();
    }
}