题解 | #牛群的回文队列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
     public String longest_palindrome_cow_queue(String s) {
        int n = s.length();
        // 用于记录从dp [i...j]是否为回文子串
        boolean [][] dp = new boolean[n][n];
        // 最大子串长度
        int maxLen = 0;
        // 最大子串的起始位置
        int begin = 0;
        // 单个字符一定是回文，直接返回
        if(s.length()<2){
            return s;
        }
        // dp初始化，长度为1的一定是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int  left= 2; left <= n; left++) {
            for (int i = 0; i < n; i++) {
                // 右边界在哪个位置
                int j = left+i-1;
                // 如果右边界大于n长度
                if(j>=n){
                    break;
                }
                // 判断字符是否相同 不相等设置false
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    // 如果字符相同并且长度小于3，那么必定是true
                    if(j-i<3){
                        dp[i][j] = true;
                    }else {
                        // 如果大于等于3，需要判断其他值
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen= j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}

本题知识点分析：

1.动态规划

2.数学模拟

3.API函数

4.数组遍历

本题解题思路分析：

1.先进行一些特殊判断，比如长度为1的情况，直接返回s

2.dp数组代表从i 到 j 是否是回文子串

3.dp 初始化 每一个长度为1的字符都是true

4.长度可以从2开始到n

5.左边界从0开始，右边界可以通过计算 left+i-1得到

6.如果右边界大于n长度 直接break;

7.判断字符是否相同 不相等设置false

8.如果字符相同并且长度小于3，那么必定是true

9.如果大于等于3，需要判断其他值

10.dp为真并且长度大于maxLen,更新最大长度，记录此时左边界索引

本题使用编程语言: Java

时间复杂度：O(n2) 暴力是O(n3) 有O(n)的解法，需要Manacher 算法 ，这是数学，一般面试不会要求那么细

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~