题解 | #牛牛的回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLength = 1;
        // 初始化所有长度为1的必为true
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 外层循环 字符串长度控制
        for (int len = 2; len <= n; len++) {
		  // 为什么等号可以取，因为end还是会作-1,因此不会越界 例如 n = 5, len = 2, start = 3 3+2-1=4 
            for (int start = 0; start <= n - len; start++) {
                // 右边界控制
                int end = start + len - 1;
			  // 如果首尾字符相等，判断中间字符
                if (s.charAt(start) == s.charAt(end)) {
				  // len=2表明初始化的时候，只有首尾字符不用判断中间字符
				  // 如何判断中间字符，用dp数组即可
                    if (len == 2 || dp[start + 1][end - 1]) {
					  // 是回文那么更新最大长度
                        maxLength = Math.max(maxLength, len);
					  // 该位置首尾字符标记为true,表示回文
                        dp[start][end] = true;
                    }
                }
            }
        }
        return maxLength;
    }
}

本题知识点分析：

1.动态规划

2.字符串回文判断

3.数组遍历

4.API函数Math.max

本题解题思路分析：

1.利用dp数组进行回文判断

2.初始化长度为1的子串肯定是回文

3.外层循环 字符串长度控制

4.如果首尾字符相等，判断中间字符

5.len=2表明初始化的时候，只有首尾字符不用判断中间字符 如何判断中间字符，用dp数组即可

6.是回文那么更新最大长度，该位置首尾字符标记为true,表示回文

本题使用编程语言: Java

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