如何编写代码实现一个字符串的最长回文子串

/**
 * @author pxu
 * @create 2021/4/7-2:28 下午
 */
public class Nc017 {


    public static void main(String[] args) {

        String str = "abc1234321ab";

        Nc017 nc017 = new Nc017();

        int longestPalindrome = nc017.getLongestPalindrome(str, str.length());
        
        System.out.println(longestPalindrome);

    }


    public int getLongestPalindrome(String A, int n) {

        /**
         * 这个问题用的是从上而下的动态规划求解方法，讲求字符串A的最长回文子序列问题，
         * 转换成三个子问题：求A.sutString(1,A.length)、求A.sutString(0,A.length-1)
         * 以及A.sutString(1,A.length-1)三种情况的解，并比较三种情况的解，得到最优解
         * 
         * 首先验证参数合法性，在定义一个二维数组用于记录已经求结果的子问题的解，主要的求解过程
         * 在helper方法中
         */

        switch (n)
        {
            case 0:
                return 0;
            case 1:
                return 1;
            default:
            {
                Optimum[][] dp = new Optimum[n][n];
                Optimum optimum = helper(A, dp, 0, n - 1);
                return optimum.len;
            }
        }

    }

    public Optimum helper(String theStr, Optimum[][] solArr, int start, int end)
    {
        /**
         * 此方法的最终返回结果
         */
        Optimum res = null;

        /**
         * 参数不合法直接返回null
         */
        if(start<0 || end<0 || start>=solArr.length || end>=solArr.length || start > end)
            return null;
        else
        {
            /**
             * 如果当前子问题已经被求结果，直接返回在dp中记录的结果
             */
            if(solArr[start][end]!=null)
            {
                return solArr[start][end];
            }
            else if (start == end)
            {
                /**
                 * 用于处理只有一个字符的子串的情况
                 */
                res = new Optimum(start,end,theStr);
            }
            else
            {
                /**
                 * 分别求解三种子问题的最优解
                 */
                Optimum left = helper(theStr, solArr, start + 1, end);
                Optimum right = helper(theStr, solArr, start, end - 1);
                Optimum mid = helper(theStr, solArr, start + 1, end - 1);

                /**
                 * 如果start位置和end位置的字符相等，那么需要对A.sutString(1,A.length-1)类型问题
                 * 的解进一步处理
                 */
                if(theStr.charAt(start) == theStr.charAt(end))
                {
                    /**
                     * 如果start和end是相邻的整数，如6和7，那么从上面的代码可以知道此时mid一定是null，
                     * 但是此时的start位置和end位置的字符相等，那么mid解应该是一个长度为2的回文串。
                     * 
                     * 如果mid不是null，并且mid解的回文串的起止位置刚好和start和end相邻，那么说明该解
                     * 可以被进一步延长，吧start和end位置的字符也包括进去。
                     */
                    
                    if(mid == null || (mid.start == start+1 && mid.end == end-1))
                        mid = new Optimum(start,end,theStr);
                }

                /**
                 * 比较并获取最优解
                 */
                Optimum finest = left;
                if (mid!=null && mid.len>finest.len)
                    finest = mid;
                if (right!=null && right.len>finest.len)
                    finest = right;

                res = finest;

            }
        }

        /**
         * 讲此子问题的最优解记录到数组中
         */
        solArr[start][end] = res;

        /**
         * 返回解
         */
        return res;

    }


}

class Optimum {
    /**
     * 此类代表原始字符串的一个子串的最长回文子串
     * @param start 此回文串在原始字符串中的起始偏移量
     * @param end 此回文串在原始字符串中的终止偏移量
     * @param len 此回文串的长度
     * @param str 此回文串本身
     */

    int start = 0;
    int end = 0;
    int len = -1;
    String str = "";

    @Override
    public String toString() {
        return "Solution{" +
                "start=" + start +
                ", end=" + end +
                ", len=" + len +
                ", str='" + str + '\'' +
                '}';
    }

    public Optimum() {
    }
    
    public Optimum(int start, int end, String oriStr) {
        this.start = start;
        this.end = end;
        this.len = end-start+1;
        this.str = oriStr.substring(start,end+1);
    }
}