首先声明的是这种解法非常非常的原始和不优雅，甚至比暴力递推还要臭长。
对于最长回文子串这种经典的老题目，有很多亮眼的解法，比如与逆序串取交集。
但我们解决问题不能总是依靠这种眼前一亮（虽然很少亮那么一下），我们应该有一些通用的思考方法，可以用来解决绝大部分问题。
问题的解决都有递归和递推的两种描述，而递归描述可以更加直观的表达出我们的思路，可读性更强。
在递归描述中，我们只需要告诉计算机，每一步需要做什么。
暴力解法的根本也是用相同的逻辑尝试所有的可能，可以很容易的用递归描述表示出来。
我们需要考虑的是，如何定义递归函数的语义，可以遍历整个解空间，以及遍历的边界是什么。
递归函数定义出来后，函数的参数便是遍历解空间的前进坐标，我们找出可以唯一确定某个解的坐标的集合，如果存在重复计算可以根据该集合建立缓存（一个n维的数组，每个维度代表一个参数，沿着这些维度前进就是递归过程中沿着递归调用前进）。
如果整个递归过程都不存在重复计算，那么说明，我们的暴力法确实太暴力了，我们把解决问题的步骤分割的太小了。
这样我们应该尝试将递归函数的语义扩大，或者考虑分治，以减少递归调用的深度。
上述过程就是从暴力法演进到 DP 的思路，个人习惯先暴力，后优化，思路会比直接想高效的解法更清晰。
所以这里只放最基础的暴力递归的代码，这是后面优化的根基。正确性可以保证，leetcode验证过了，虽然很慢：
public class LongestSubString { public static void main(String[] args) { LongestSubString l = new LongestSubString(); String source = "cbabd"; System.out.println(l.longestPalindrome(source)); } int maxLength = 0; String ans = ""; public final String longestPalindrome(String s) { //空指针检查 if (s == null || s.length() == 0) { return ""; } search0(0, 1, -1, 2, s); search1(0, 1, 1, s); //存在长度大于 1 的回文串，返回 if (maxLength > 1) { return ans; } //不存在长度大于 1 的回文串，返回第一个字符 return s.substring(0, 1); } /** * @Author Nxy * @Date 2020/3/10 23:32 * @Description 寻找中点为两个相同字符的最长回文串 */ private final void search0(int mid1, int mid2, int left, int depth, String source) { //边界条件1，中点越界 if (mid2 >= source.length()) { return; } char mid1C = source.charAt(mid1); char mid2C = source.charAt(mid2); //略过两中点不相等的情况 if (mid1C != mid2C) { search0(mid2, mid2 + 1, mid1, 2, source); return; } int right = mid2 + mid1 - left; //边界条件2，回文串越界 if (left < 0 || right >= source.length()) { if (depth > maxLength) { ans = source.substring(left + 1, right); maxLength = depth; } search0(mid2, mid2 + 1, mid1, 2, source); return; } char leftC = source.charAt(left); char rightC = source.charAt(right); //边界条件3，回文终止 if (leftC != rightC) { if (depth > maxLength) { ans = source.substring(left + 1, right); maxLength = depth; } search0(mid2, mid2 + 1, mid1, 2, source); return; } search0(mid1, mid2, left - 1, depth + 2, source); } /** * @Author Nxy * @Date 2020/3/10 23:34 * @Description 寻找中点为单个单独字符的回文串 */ private final void search1(int left, int mid, int depth, String source) { //边界条件1，中点越界 if (mid == source.length()) { return; } //边界条件2，回文越界 if (left < 0 || mid * 2 - left >= source.length()) { if (depth > maxLength) { ans = source.substring(left + 1, mid * 2 - left); maxLength = depth; } search1(mid, mid + 1, 1, source); return; } char leftChar = source.charAt(left); char rightChar = source.charAt(mid * 2 - left); //边界条件3，回文终止 if (leftChar != rightChar) { if (depth > maxLength) { ans = source.substring(left + 1, mid * 2 - left); maxLength = depth; } search1(mid, mid + 1, 1, source); return; } search1(left - 1, mid, depth + 2, source); } }