原题链接
5、最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
示例 3：
输入：s = “a”
输出：“a”
示例 4：
输入：s = “ac”
输出：“a”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
如果 s = a 那么最大回文串是：a如果 s = bab 那么最大回文串是：bab如果 s = bac 那么最大回文串是：a如果 s = dbacd 那么最大回文串是：a找规律如果 一个字符串的子集（i~j）是 回文串 那么他的 （i-1~j+1） 是不是回文串取决于 i-1位置的字符是否和 j+1的字符相同你先品下 仔细理解下记住：当子集是回文串的时候 才能继续扩大回文串的范围
三：Java代码package xyz.fudongyang.classic;public class Leet_code_5_test { public static void main(String[] args) { String s = "abcba"; System.out.println(subString(s)); } private static String subString(String s) { // 把字符串的长度先存起来 可以减少jvm的指针调用与编译 因为经常会用到这个长度 int length = s.length(); // 如果字符串就一个 那么最大回文串就是本身 if (length < 2) { return s; } // dp数组 记录 一维数组 从i~j位置是否是回文串 boolean[][] dp = new boolean[length][length]; int maxLen = 1; int begin = 0; char[] chars = s.toCharArray(); for (int i = 0; i < length; i++) { dp[i][i] = true; } // 这个L不太好解释 就是 因为 i~i已经初始化了 我们只需要i~i+1 所以 我们从 2开始初始化 for (int L = 2; L <= length; L++) { for (int i = 0; i < length; i++) { // i是左边界 j是右边界 int j = i + L - 1; if (j >= length) { break; } // 如果两个字符串不相同 不可能再扩大范围了 if (chars[i] != chars[j]) { dp[i][j] = false; } else { // 特殊情况： 如果 aa 则为true 如果 bab 则为true if (j - i <= 2) { dp[i][j] = true; } else { // dp公式 如果上一个子集是回文串 并且 后两个字符相同 则为大回文串 dp[i][j] = dp[i + 1][j - 1]; } } // 如果本次dp成功了 则我们记录最大值 if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); }}