题解 | #最长回文子串#

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

}