题解 | #最长回文子串#

最长回文子串

https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af

import java.util.*;


public class Solution {

    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public static int getLongestPalindrome (String A) {
        // write code here

        int res =  Math.max(maxLength(2, A),
                            maxLength(3, A));

        return res;
    }

    private static int maxLength( int initLength, String A) {
        if (A.length() < initLength) {
            return 1;
        }

        List<Helper> initList = new ArrayList<>();
        for (int i = 0; i < A.length() - initLength + 1; i++) {
            String subStr = A.substring(i, i + initLength);
            if (match(subStr)) {
                initList.add(new Helper(subStr, i));
            }
        }

        if (initList.size() == 0) {
            return 1;
        }

        return Math.max(initLength, maxLength(A, initList, initLength + 2));
    }

    private static int maxLength(String A, List<Helper> list, int length) {


        if (length > A.length()) {
            return 0;
        }

        List<Helper> helperList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            Helper helper = list.get(i);
            if (helper.beginPos - 1 < 0 || helper.beginPos - 1 + length  > A.length()) {

                continue;
            }

            String subStr = A.substring(helper.beginPos - 1, helper.beginPos + length - 1);

            if (match(subStr)) {

                helperList.add(new Helper(subStr, helper.beginPos - 1));
            }
        }

        if (helperList.size() == 0) {
            return 0;
        }
        return Math.max(length, maxLength(A, helperList, length + 2));

    }


    private static boolean match(String sub) {


        int length = sub.length();

        for (int i = 0; i < length / 2; i++) {
            if (sub.charAt(i) != sub.charAt(length - i - 1)) {
                return false;
            }
        }

        return true;
    }
    public static class Helper {
        private String subString;
        private int beginPos;
        public Helper(String subString, int beginPos) {
            this.subString = subString;
            this.beginPos = beginPos;
        }
    }

}

全部评论

相关推荐

醒工硬件:1学校那里把xxxxx学院去了,加了学院看着就不像本校 2简历实习和项目稍微精简一下。字太多,面试官看着累 3第一个实习格式和第二个实习不一样。建议换行 4项目描述太详细了,你快把原理图贴上来了。比如可以这样描述:使用yyyy芯片,使用xx拓扑,使用pwm控制频率与占空比,进行了了mos/电感/变压器选型,实现了xx功能 建议把技术栈和你做的较为有亮点的工作归纳出来 5熟悉正反激这个是真的吗
点赞 评论 收藏
分享
02-09 10:51
已编辑
门头沟学院 Java
Java抽象带篮子:考完研冲春招可以看看我的置顶帖子,里面写了怎么写简历,怎么包装实习经历,还有八股笔记资料和速成的高质量项目话术呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务