【算法题】分割回文串
盖世阿萌 人气:2题目：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
举例：
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
解题思路：
再举个稍微长一点的例子吧，比如aabcc，我第一眼看到之后用我那普通人类的头脑开始列方案了：
单独一个字符是回文串：a|abcc
然后分析abcc，单独切一个a是回文：a|bcc，（ab，abc和abcc都不是回文就不考虑这三种切法了（因此对于abcc就a|bcc这一种
再来bcc，单独一个b是回文：b|cc，（bc，bcc也不是回文（因此对于bcc就b|cc这一种
最后cc，单独一个c是回文：c|c，或者两个c也构成了回文：cc|
c|c中，后面这个c，再切它就是c|，所以现在就和cc|一样分到底了，因为“|”后面是空的。
整理一下，【a，b，c，c】和【a，b，cc】是这次的结果，但还远没有结束！
因为是从a后面开始分割的，接下来可以从aa|bcc，aab|cc，aabc|c，aabcc|的角度来切，每次切完固定 | 前面的部分，用同样的切切法分析 | 后面的部分。
到这里似乎有了点什么灵感呢~
每次都从头开始遍历，一个字符两个字符三个字符这样检查，如果是一段回文那就切开，切点后面的部分用同样的方法；
如果切点后是空了就返回一个空list，在返回的不同路线上把前面的切头加在这个list的前面，一直返回到路线的最开始就是结果了。
表达能力有点捉鸡，总之就是先从头到尾切切切，再从尾到头加加加的过程，科学一点的说法就是“分治”。把大字符串切成小字符串，小字符串切到空。
可以用迭代（栈）或者是递归的方法。
贴一个JAVA代码：
class Solution {
public List<List<String>> partition(String s) {
boolean[][] dp=new boolean[s.length()][s.length()];
for(int len=1;len<=s.length();len++){
for(int i=0;i<=s.length()-len;i++){
if(len==1)dp[i][i]=true;
else if(s.charAt(i)==s.charAt(i+len-1)&&(len==2||dp[i+1][i+len-2])){
dp[i][i+len-1]=true;
}
}
}
return solution(s,0,dp);
}
public List<List<String>> solution(String s,int start,boolean[][] dp){
ArrayList<List<String>> list=new ArrayList<>();
if(start==s.length()){//切到空空如也，就返回一个空list，让前辈们往上加吧
List<String> li=new ArrayList<>();
list.add(li);
return list;
}
for(int i=start;i<s.length();i++){//非常认真地一个一个字符找，看能不能切
if(dp[start][i]){//啊，从start到i是回文！切它！
String first=s.substring(start,i+1);
for(List<String> li:solution(s,i+1,dp)){
li.add(0,first);//把返回得到的一到多个list前面都分别加上切掉的部分
list.add(li);
}
}
}
return list;
}
}
PS：这里呢，为了方便判断string的一段是不是回文，提前用动态规划法做了一个dp数组，如果这段是回文就记录为true。
1、回文长度 len 是1、2、3、4、...、length。
2、回文的起点 i 是0、1、2、3、...、length-len（后面长度不足len了就肯定不是len长的回文了）。
3、如果长度len为1，那就一个字符了肯定是回文了；
如果长度为2，且起点的字符==终点的字符，起点挨着终点，他俩还相等，那稳了；
如果长度大于2，且起点的字符==终点的字符，如果他们内层是回文那就是回文了，dp[i+1][i+len-2]表示从起点+1到终点-1的字符串是否是回文。
boolean[][] dp=new boolean[s.length()][s.length()];
for(int len=1;len<=s.length();len++){
for(int i=0;i<=s.length()-len;i++){
if(len==1)dp[i][i]=true;
else if(s.charAt(i)==s.charAt(i+len-1)&&(len==2||dp[i+1][i+len-2])){
dp[i][i+len-1]=true;
}
}
}
PPS：去LeetCode写一哈吧，一定要动手才知道会不会呀！
https://leetcode-cn.com/problems/palindrome-partitioning/
加载全部内容