题解 | #最长回文子串#

最长回文子串

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;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务