题解 | #牛群编号的回文顺序II#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode maxPalindrome (ListNode head) {
        if (head == null) {
            return head;
        } else if (head.next == null) {
            return head.next;
        }
        StringBuilder sb = new StringBuilder();
        ListNode cur= head;
        while (cur != null) {
            sb.append(cur.val + "");
            cur =cur.next;
        }
        //求这个最大的连续回文子链表
        int len = sb.toString().length();
        int maxlen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        char[] charArray = sb.toString().toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int l = 2; l <= len; l++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 l 和 i 可以确定右边界，即 j - i + 1 = l 得
                int j = l + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][l] == true 成立，就表示子串 s[i..l] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxlen) {
                    maxlen = j - i + 1;
                    begin = i;
                }

            }

        }

        if(begin==0&&begin+maxlen==sb.toString().length()){
            return new ListNode(-1).next;
        }
         ListNode ans =head;
         maxlen = begin+maxlen;
        while(begin >0){
            ans=ans.next;
            begin--;
        }
        ListNode tail = head;
         for(int p=0;p<maxlen-1;p++){
            tail=tail.next;
        }
        tail.next=null;
        //判断
        return ans;

    }
}