算法路上多坎坷，习得变幻悟真谛

聊聊恶心的回文子串

引言那就刷一下吧最笨法（暴力法）动态规划解法两栈一列法

引言

熟悉算法的朋友应该都了解算法中有一大块关于字符串的题，鉴于我们在程序设计语言中体会到的字符串，潜意识里很容易就把这部分题划分为简单的一类。 现实总是喜欢给你一巴掌，这类题型中其实也有很多让人恶心的题，其中臭名昭著的就有 回文子串 系列。

那就刷一下吧

作为互联网界的优秀青年，我们勇往直前，为了理想，可卑可抗，逆风也要上。就让我们通过刷题慢慢盘一下这恶心的 回文子串 大家庭(以后亲切称为“小回一家”)

今天要介绍的小回一家成员之一，也是各种场合出镜率最高选手，最长回文子串同学。 为了深入了解这位同学，我们选取他出镜的力扣原题之一(见下图）进行剖析，并依次从多个角度展开攻略

分析 拿到题目，我们首先了解到该题目几个关键点： 输入条件为字符串最长回文子串

这里面可能有个词大家并不知道是什么含义，什么是回文子串？这里举个🌰说明一下。

比如想题目中陈述的，“babad”这个字符串中子串“bab”、“aba”，或者是这个字符串中的任意单一字符构成的字符串，例如“b”,均可称为回文子串，这里回文子串初略的来说就是字符串有一个“对称轴”。

专业点说就是回文串从首尾分别使用两个指针，头指针尾指针，两指针按照每次步数一致向对方移动，每次走到的数组下标对应的值都相等，该字符串即为回文串。

伪代码表示为：

STRAT = 0 END = STRING - 1 FOR STRING IF STRING[i++] != STRING[STRING.length--] RETURN 不是回文串 RETURN 是回文串

最笨法（暴力法）

思路

拿到题目之后，想到这里面是要求最大回文子串，那我们就把字符串的子串全部求出来，然后判断这些字串那些是回文子串。 同时，题目中要求我们输出的是最长的回文子串，于是我们想到用两个空间分别记录子串的长度，以便后续回文串之间的比较，然后另一个空间记录目前最长的回文子串。 最终，在这些回文子串分别比较之后，返回一个最长的回文子串便是我们要的答案啦！

经过以上思路，我们想到如何将字符串的子串全部求出来呢？我们以题目中的第一个字符串"babad"为例，观察下面的字符串结构： 我们每次移动i，在此基础上，j遍历到i之前的下标为止(一个字符即为回文子串，因此无需遍历到i)，这里我们便获得从0~i这一段的所有子串，由于我们每次将i向后移动一个，因此我们目前了解通过二层循环便可实现该过程，至于判断是否为回文串，具体看下面代码注释。

代码 package string; /** * 最长回文子串 * @author 测开浅迹 */ public class LongestPalindrome { /** * 获取字符串最大回文子串 * @param str 待传入字符串 * @return */ public String getLongestPalindrome(String str){ int maxLength = 0; char[] charArray = str.toCharArray(); //创建一个记录当前最大回文子串的变量，避免所判断字符串的最大回文串长度不超过1，变量初始化值为第一个字符创建的字符串对象 String longestPalindrome = new String(charArray,0,1); //双层循环遍历出输入字符串的所有子串，分别进行判断是否是回文子串 for(int i = 0; i <= charArray.length-1; i++){ for(int j = 0; j <= i; j++){ //判断当前子串是否是回文子串 if(isPalindrome(charArray, j, i)){ //当前回文子串的长度是否大于已记录最大长度，如果是的话，则更新最大长度，且记录当前最大回文子串 if((i-j+1) > maxLength){ maxLength = i-j+1; longestPalindrome = new String(charArray,j,i+1); } } } } return longestPalindrome; } /** * * @param ch 通过字符串获得的字符数组 * @param start 子字符串开始下标 * @param end 子字符串结束下标 * @return */ public boolean isPalindrome(char[] ch, int start, int end){ //如果子串长度是1不做判断，单个字母必定是回文子串 if(ch.length == 1) return false; //使用双层循环各自的下标确定当前的子字符串，以进行判断 for(; start < end; start++){ //根据回文串字符对称的原则，由子字符串首尾依次判断字符是否相同，如果遍历到最后只剩一个字符或者两下标相邻均符合对称原则，则为回文子串。 if(ch[start] != ch[end--]) return false; } return true; } }

复杂度分析

时间复杂度：$$O(N^3)$$ 空间复杂度：$$O(1)$$

动态规划解法

两栈一列法