LeetCode刷题最好按照标签归类来刷，本文主要对leetcode上的回文串问题做一个梳理。
Leetcode上回文串经典题如下：
回文串核心问题
什么是回文串
回文字符串指的是字符串从左到右 和从右到左是一样的。
- 单个字符肯定是回文串
- 两个字符如果相等是回文串
- 多个字符，如果首末位相等，中间是回文，那么整体是回文
概括三种情况：
对于一个字符串s，从下标i到j的子串，判断其回文。flag[i][j]表示i~j是否为回文。
s[i]==s[j] &&(flag[i+1][j-1] || j-i<=1)
由此可见flag[i][j]依赖于flag[i+1][j-1]，我们要计算出flag[i][j]必须先求出flag[i+1][j-1]，而这个位置是在(i,j)的下方，因此我们填充flag这个表格数组的时候遵从的是从左到右从下到上的生成方式。
LC5 最长回文子串
使用动态规划 dp[i] 表示从i到len-1位置的最长回文子串长度。
求出一个dp数组，保存[i,j]是否为回文的信息，对于一个从i到j的子串，如何判断它是否为回文串。
如图1，当固定i=3时，j可以从3到7进行遍历，每次j遍历的过程中会计算出i到j是否是回文，这样再下次计算的时候，直接使用，不用重复计算。
如当i=3,j=5时，s[i]=s[j]，且flag[4][4]是true，那么dp[i]此时就可以进行更新，dp[i]=5-3+1=3；当j不断向后继续遍历，dp[i]的值就会不断更新。
/**
**为什么不能从i=0到i=n-1 而是要从i=n-1到i=0因
**flag[i][j]依赖于 flag[i+1][j-1]因此 要先计算出i+1行 ,j-1列才能推算 出i,j
**因此方向为从下到上，从左到右
**/
public String longestPalindrome(String s) {
if(s==null || s.length()==0){
return "";
}
int n=s.length();
boolean[][] flag=new boolean[n][n];
int[] dp=new int[n];
for(int i=0;i<n;i++){
dp[i]=1;
}
char[]t =s.toCharArray();
//记录长度
int res=0;
//记录起始位置
int index=-1;
for(int i=n-1;i>=0;i--){
for(int j=i;j<n;j++){
//[i,j]是回文，dp[i]表示[i,len-1]上的最长回文串，dp[i]有一个初始值
//现在找到了一个 i~j 长度为j-i+1， j一直变化，能够找到以i开头的最大长度
if(t[i]==t[j]&& (j-i<=1||flag[i+1][j-1])){
flag[i][j]=true;
//从i到j是回文，那么[i,len-1]的最长回文 至少有j-i+1;
dp[i]=Math.max(dp[i],j-i+1);
}
}
if(res<dp[i]){
res=dp[i];
index=i;
}
}
return s.substring(index,index+res);
}
LC9 回文数
我们可以将数字转成字符串，然后利用首尾指针进行判断，一旦不等说明不是回文，但是这样要耗费额外的空间。
我们可以从末尾构建反转后的数字，再与原来的数进行比较，如果是相等，那就是回文。负数肯定不是回文。
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int tmp = x;
//存储反转后的数字，可能溢出，用long
long val = 0;
while (x > 0) {
// 末尾数字放在前头
val = val * 10 + x % 10;
x = x / 10;
}
return tmp == val;
}
}
LC131 分割回文串i
如果要求出所有的分割情况，而不要求最小的，则应该使用递归回溯。
实际上我们是在一个隐式树结构上进行搜索，可以使用深度优先搜索。
考虑以下例子，对于一个字符串 s=“aaaba”，我们可以做如下选择：
- 第一次从第0个字符开始
可以选择一个字符组成a，也可以选择两个字符aa，直到选择最后一个字符，不能再进行选择了，退出，当然在每次选择完以后，都要判断当前的字符串是不是回文，是回文的话，才从已经选择完的后面一个位置，进行下一轮选择。 - 第二次选择从第一个字符开始
那么也可以在此基础上向后扩展选择第1个，第2个，，直到选择的字符到达字符串末尾。按照第一次的方式再进行计算。
…
编码的话，实际就是把上面的描述用程序语言翻译下。
递归回溯
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
int len = s.length();
dfs(s, len, 0, new ArrayList<>());
return res;
}
void dfs(String s,int len, int index, List<String> list) {
if (index >= len) {
if (index == len) {
res.add(new ArrayList<>(list));
}
return;
}
//从index位置开始，可以选择的候选人有 ，index+1,index+2,直到index+i=len
for (int i = 1; index + i <= len; i++) {
//substring 是左闭右开
String tmp = s.substring(index, index + i);
if (isValid(tmp)) {
//tmp有效，将其先加入列表
list.add(tmp);
//如果当前选择的字符串是回文，那么下一次就从index+i处开始选择
dfs(s,len, index + i, list);
//回溯 tmp有效，重新进行选择，可能选择tmp后一个字符的位置，需要把之前的结果撤销
list.remove(list.size() - 1);
}
}
}
//校验是否是回文
public boolean isValid(String s) {
int left = 0;
int right = s.length()-1;
while (left < right){
if(s.charAt(left)==s.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}
记忆化搜索
上面我们在计算从i到j是否是回文的时候，有重复计算，实际上可以存储i-j的回文结果，用记忆化搜索来实现。具体如下：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
int len = s.length();
boolean[][] flag = new boolean[len][len];
dfs(s, len, 0, new ArrayList<>(),flag);
return res;
}
void dfs(String s,int len, int index, List<String> list,boolean[][] flag) {
if (index >= len) {
if (index == len) {
res.add(new ArrayList<>(list));
}
return;
}
for (int i = 1; index + i <= len; i++) {
String tmp = s.substring(index, index + i);
//使用flag数组来记录从i到j是否是回文，避免重复计算，能够快速剪枝
if (flag[index][index+i-1] || isValid(tmp)) {
flag[index][index+i-1] = true;
list.add(tmp);
dfs(s,len, index + i, list,flag);
list.remove(list.size() - 1);
}
}
}
public boolean isValid(String s) {
int left = 0;
int right = s.length()-1;
while (left < right){
if(s.charAt(left)==s.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}
能看到处理时间上提高了。
递归回溯2
也可以换另外一种写法，我觉得第一种写法可能更好理解一些，其实可以发现很多回溯问题，都是这种套路（比如ip问题），后续会更新回溯专题。
public static List<List<String>> partition(String s) {
List<List<String>> res=new ArrayList<>();
List<String> cur=new ArrayList<>();
dfs(res,cur,s);
return res;
}
/**
*
* @param res 存储每一趟遍历的符合要求的记过
* @param cur cur记录一趟遍历，存储的结果
* @param s
*/
public static void dfs(List<List<String>>res,List<String> cur,String s){
if(s.length()==0){
res.add(new ArrayList<>(cur));
}
int len=s.length();
for(int i=1;i<=len;i++){
String s1=s.substring(0,i);
if(isPalindrome(s1)){
cur.add(s1);
String s2=s.substring(i);
dfs(res,cur,s2);
cur.remove(cur.size()-1);
}
}
}
public static boolean isPalindrome(String s){
if(s==null||s.length()==0){
return false;
}
int j=s.length()-1;
int i=0;
while(i<j){
if(s.charAt(i)==s.charAt(j)){
i++;
j--;
}else{
return false;
}
}
return true;
}
LC132 分割回文串ii
求最小的切分，使得分割后每个子串都是回文的。
状态 dp[i] 表示从i到n-1的最小回文分割数目，
那么对于任意的一个j,j属于[i,n-1],如果[i,j]是回文的话，则
dp[i]=min(dp[j+1]+1) j从i到n-1,且当j=n-1时，dp[n]=-1;
因此只要遍历一遍从i到n-1的j，求取最小的dp[i]即可。
如果i-j是回文，那么dp[i]= 1+dp[j+1]
如果回文的范围扩大，比如i到j+2都是回文，那么dp[i]=1+dp[j+3]
对于一个位置i，它的最小切分为
min(dp[j] )+1 其中 j=i…len-1;
//和最长递增子序列很相似
public int minCut(String s) {
int len=s.length();
boolean[][] flag=new boolean[len][len];
//dp[i]代表[i,len-1]的切成回文的最小分割数
int[] dp=new int[len+1];
// getdp(s,flag,len);
//从右往左进行计算
dp[len]=-1;
for(int i=len-1;i>=0;i--){
dp[i]=Integer.MAX_VALUE;
for(int j=i;j<len;j++){
//[i,j]是回文
if(s.charAt(j)==s.charAt(i) && (j-i<=1 || flag[i+1][j-1])){
flag[i][j]=true;
dp[i]=Math.min(dp[j+1]+1,dp[i]);
}
}
}
return dp[0];
}