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

1. 题目考察的知识点

链表的基本操作，动态规划

2. 题目解答方法的文字分析

基本解题思路：当head是null，返回空链表；当原链表只有一个元素的时候，返回空链表，此时是回文的。剩下的情况就只需要判断原链表是否是回文串即可。首先将整个链表所代表的值用stringBuilder类型的sb存下来，然后用动态规划求出sb字符串的最大回文子串的首尾位置。最后通过首尾位置截取原链表的子链表。

字符串求最大回文子串：对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。根据这样的思路，我们就可以用动态规划的方法解决本题。我们用dp[i][j] 表示 sb[i..j] 是否是回文串,表示字符串 sb 的第 i 到 j 个字母组成的串,为true就是回文串。然后因为一个字符串就是回文串，索引初始化时所有长度为 1 的子串都是回文串。所以由此我们可以得出动态规划方程： dp[i][j]=dp[i+1][j-1]^(sb_i==sb_j)即只有 sb[i+1:j−1]是回文串，并且 sb 的第 i 和 j 个字母相同时，sb[i:j]才会是回文串。 最终答案即是dp[i][j]中j−i+1（即子串长度）的最大值。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

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;

    }
}