给定一个字符串s，分割s使得s的每一个子串都是回文串
返回所有的回文分割结果。（注意：返回结果的顺序需要和输入字符串中的字母顺序一致。）
[编程题]分割回文串
java 回溯大法
public class Solution {
/**
*
* @param s string字符串
* @return string字符串ArrayList<ArrayList<>>
*/
private ArrayList<ArrayList<String>> ans = new ArrayList<ArrayList<String>>();
public ArrayList<ArrayList<String>> partition (String s) {
// write code here
trackBack(s, 0, ans, new ArrayList<String>());
return ans;
}
// 回溯分割字符串
public void trackBack(String s, int start, ArrayList<ArrayList<String>> ans, ArrayList<String> list){
if(start == s.length()){
ans.add(new ArrayList<>(list));
return ;
}
for(int i=start;i<s.length();i++){
String temp = s.substring(start,i+1);
if(!isPalindrome(temp)) continue;
list.add(temp);
trackBack(s,i+1,ans,list);
list.remove(list.size()-1);
}
}
// 判断是否为回文字符串
public boolean isPalindrome(String str){
int left = 0, right = str.length()-1;
while(left < right){
if(str.charAt(left++) != str.charAt(right--)) return false;
}
return true;
}
}
发表于 2021-10-02 11:21:58
回复(0)
用回溯法，递归求解。具体解析看下面代码的注释。
import java.util.ArrayList;
/** 分割回文串
*/
public class SplitPalindromeString {
/**
*
* @param s string字符串
* @return string字符串ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<String>> partition (String s) {
// 存放返回的结果数组
ArrayList<ArrayList<String>> result = new ArrayList<>();
// 保存当前正在分割的一个数组集合
ArrayList<String> list = new ArrayList<String>();
findPalindrome(result, list, s);
return result;
}
/**
* 递归实现查找所有的子字符串
* @param result 结果数组
* @param list 当前处理的数组集合
* @param s 当前要处理的字符串
*/
private void findPalindrome(ArrayList<ArrayList<String>> result, ArrayList<String> list, String s) {
if (s == null || s.length() == 0) {
//当前的分割情况下，已经找完了所有的回文字符串
// 注意： 治理不能直接 result.add(list)；
result.add(new ArrayList<>(list));
return;
}
// 对字符串 s 从1个到n 分割成字符串，如果是回文的，通过list.add(回文串), 再将进行递归查找后面的回文串，下面是回溯刚才的add 操作
// 因为对于s.substring(0,); 是永远取不到 i 值的，所以这里要注意 i 的下标取值范围
for (int i = 1 ; i <= s.length(); i++) {
String subStr = s.substring(0, i);
if (isPalindrome(subStr)) {
// subStr 是回文串
list.add(subStr);
// 把 s 剩下的部分 作为下一层递归的参数
findPalindrome(result, list, s.substring(i));
// 回溯： 恢复刚才递归前的状态, 即删除当前层次下，最新插入的一个字符串（因为是递归，在递归中插入list的数据必定已经被此语句也删除了相关的一个字符串）
list.remove(list.size() - 1);
}
}
}
/**
* 判断 s 是否是回文串
* @param s
* @return
*/
private boolean isPalindrome (String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
SplitPalindromeString splitPalindromeString = new SplitPalindromeString();
String s = "a";
ArrayList<ArrayList<String>> result = splitPalindromeString.partition(s);
}
}
发表于 2020-09-19 00:36:42
回复(0)
// dp的方式
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
Map<String, ArrayList<ArrayList<String>>> dp = new HashMap<>();
return partition(s, dp);
}
private boolean isPalindrome(String s) {
for (int left = 0, right = s.length() - 1; left < right; left++, right--) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
}
return true;
}
public ArrayList<ArrayList<String>> partition(String s, Map<String, ArrayList<ArrayList<String>>> dp) {
if (dp.containsKey(s)) {
return dp.get(s);
}
ArrayList<ArrayList<String>> res = new ArrayList<>();
for (int i = 1; i < s.length(); i++) {
String leftSubStr = s.substring(0, i);
if (!isPalindrome(leftSubStr)) {
continue;
}
ArrayList<ArrayList<String>> rightPartition = partition(s.substring(i, s.length()), dp);
if (rightPartition.size() == 0) {
continue;
}
for (ArrayList<String> aRight : rightPartition) {
ArrayList<String> tmp = new ArrayList<>();
tmp.add(leftSubStr);
tmp.addAll(aRight);
res.add(tmp);
}
}
if (isPalindrome(s)) {
ArrayList<String> tmp = new ArrayList<>();
tmp.add(s);
res.add(tmp);
}
return res;
}
}
发表于 2019-07-25 01:00:32
回复(0)
import java.util.ArrayList;
public class Solution {
ArrayList<String> list = new ArrayList<>( );
ArrayList<ArrayList<String>> res = new ArrayList<>( );
Boolean[][] p;
public ArrayList<ArrayList<String>> partition(String s) {
p = new Boolean[s.length()][s.length()];
//先把回文串的部分找出来 然后用p存着
for(int i=s.length()-1;i>=0;i--)
{
for(int j=i;j<s.length();j++)
{
if(s.charAt( i )==s.charAt( j ) && (j-i<2 || p[i+1][j-1]))
p[i][j] = true;
else p[i][j]=false;
}
}
//知道了哪段是回文串后直接爆搜吧
dfs( 0,s );
return res;
}
public void dfs(int k,String s)
{
if(k==s.length())
{
ArrayList<String> l = new ArrayList<>( list );
res.add( l );
return;
}
for (int i=k;i<s.length();i++)
{
if(p[k][i])
{
list.add( s.substring( k,i+1 ) );
dfs( i+1,s);
list.remove(list.size()-1);
}
}
}
}
动态规化+搜索==耗时1200多点
这样找回文串是借鉴上一题的大佬的思想，太吊了
发表于 2019-07-19 20:52:04
回复(0)
public class PalindromePartitioning { public static void main(String[] args) { ArrayList<ArrayList<String>> partition = new PalindromePartitioning().partition("abab"); for (int i = 0; i < partition.size(); i++) { System.out.println(partition.get(i)); } } public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
ArrayList<String> list = new ArrayList<>();
backtracking(0,s,result,list);
return result;
}
private void backtracking(int left,String s,ArrayList<ArrayList<String>> result,ArrayList<String> list){
if(left==s.length()){
result.add((ArrayList<String>) list.clone());
return;
}else{
for(int right=left;right<s.length();right++){
if(isPalindrome(s.substring(left, right+1))){
list.add(s.substring(left, right+1));
backtracking(right+1,s,result,list);
list.remove(list.size()-1);
}
}
}
}
private boolean isPalindrome(String t){
return new StringBuffer(t).reverse().toString().equals(t);
}
}
woweileyigenvrenershuati
发表于 2018-09-09 20:15:55
回复(0)
import java.util.ArrayList;
public class Solution { boolean[][] dp; ArrayList<ArrayList<String>> res = new ArrayList<>(); ArrayList<String> list = new ArrayList<>(); public ArrayList<ArrayList<String>> partition(String s) { dp = new boolean[s.length()][s.length()]; dfs(0, s.length(), s); return res; } void dfs(int cur, int n, String s) { if (cur == n) { res.add((ArrayList<String>) list.clone()); return; } for (int j = cur; j < n; j++) { if (s.charAt(cur) == s.charAt(j) && (cur > j - 2 || dp[cur + 1][j - 1])) { dp[cur][j]=true; list.add(s.substring(cur, j+1)); dfs(j + 1, n, s); list.remove(list.size() - 1); } } } public static void main(String[] args) { Solution a = new Solution(); ArrayList<ArrayList<String>> list = a.partition("efe"); list.forEach(e -> System.out.println(e)); }
}
发表于 2018-08-16 14:39:24
回复(0)
想不到递归还有讲究，将一些不变的量传入参数居然会复杂度过高；而要是声明为类的成员变量就可以通过。。。
import java.util.ArrayList;
public class Solution {
static String string;
static ArrayList<ArrayList<Boolean>> booleans;
public static ArrayList<ArrayList<String>> partition(String s) {
string = s;
booleans = generateList(s);
return partitionRecursive(0);
}
public static ArrayList<ArrayList<String>> partitionRecursive(int from) {
ArrayList<ArrayList<String>> resultLists = new ArrayList<>();
if (string.length() == from) {
resultLists.add(new ArrayList<>());
return resultLists;
}
for (int i = from; i < string.length(); i++) {
if (booleans.get(from).get(i - from)) {
String substring = string.substring(from, i + 1);
ArrayList<ArrayList<String>> arrayLists1 = partitionRecursive(i + 1);
for (ArrayList<String> aList :
arrayLists1) {
aList.add(0, substring);
}
resultLists.addAll(arrayLists1);
}
}
return resultLists;
}
//生成palindrome[i][j]
//现在对长度不作要求
public static ArrayList<ArrayList<Boolean>> generateList(String string) {
ArrayList<ArrayList<Boolean>> arrayLists = new ArrayList<>();
//ArrayList.get(i).get(m) 表示从i到i+m是否回文
for (int i = 0; i < string.length(); i++) {
ArrayList<Boolean> arrayList = new ArrayList<>();
arrayList.add(0, true);
if (i < string.length() - 1) {
arrayList.add(1, string.charAt(i) == string.charAt(i + 1));
}
arrayLists.add(i, arrayList);
}
for (int j = 2; j < string.length(); j++) {
for (int i = 0; i + j < string.length(); i++) {
Boolean bool = string.charAt(i) == string.charAt(i + j)
&& arrayLists.get(i + 1).get(j - 2);
arrayLists.get(i).add(j, bool);
}
}
return arrayLists;
}
}
发表于 2018-05-01 12:45:28
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
if(s.length()==0){
return result;
}
if(s.length()==1){
ArrayList<String> list=new ArrayList<String>();
list.add(s);
result.add( list );
return result;
}
for(int i=1;i<=s.length();i++){
String temp=s.substring(0,i);
//如果是回文串
if(isPalindrome(temp)){
//如果已经到头了
if(i==s.length()){
ArrayList<String> list=new ArrayList<String>();
list.add(temp);
result.add(list);
}else{//如果没到头
ArrayList<ArrayList<String>> list=partition( s.substring(i) );
for(int j=0;j<list.size();j++){
ArrayList<String> r=new ArrayList<String>();
r.add(temp);
r.addAll(list.get(j));
result.add(r);
}
}
}else{//如果不是回文串
continue;
}
}
return result;
}
public boolean isPalindrome(String s){
if(s.length()==1){
return true;
}
int index1=0;
int index2=s.length()-1;
while(index1<=index2){
if(s.charAt(index1)!=s.charAt(index2)){
return false;
}
index1++;
index2--;
}
return true;
}
}
发表于 2017-08-06 15:23:04
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
if (s == null || s.length() == 0)
return list;
int len = s.length();
boolean[][] isPalindrome = new boolean[len][len];
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len - i; ++j) {
if (i < 3) {
if (s.charAt(j) == s.charAt(j + i)) {
isPalindrome[j][j + i] = true;
}
} else {
if (s.charAt(j) == s.charAt(j + i) && isPalindrome[j + 1][j + i - 1])
isPalindrome[j][j + i] = true;
}
}
}
list = getResult(s, 0, len, isPalindrome);
for (ArrayList<String> temp : list) {
int size = temp.size();
for (int i = 0; i < size / 2; ++i) {
String tempStr = temp.get(i);
temp.set(i, temp.get(size - 1 - i));
temp.set(size - 1 - i, tempStr);
}
}
return list;
}
public ArrayList<ArrayList<String>> getResult(String s, int startIndex, int len, boolean[][] isPalindrome) {
ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
for (int i = startIndex; i < len; ++i) {
if (isPalindrome[startIndex][i]) {
if (i == len - 1) {
ArrayList<String> tempList = new ArrayList<String>();
tempList.add(s.substring(startIndex, i + 1));
list.add(tempList);
} else {
ArrayList<ArrayList<String>> subList = getResult(s, i + 1, len, isPalindrome);
for(ArrayList<String> temp : subList) {
temp.add(s.substring(startIndex, i + 1));
list.add(temp);
}
}
}
}
return list;
}
}
发表于 2017-07-25 21:05:19
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<String>>
partition(String s) {
ArrayList<ArrayList<String>> result=new
ArrayList<ArrayList<String>>();
ArrayList<String> list=new ArrayList<>();
subString(result,list,s);
return result;
}
//求s的所有子串集合，并将满足条件的集合加入到result中
public void
subString(ArrayList<ArrayList<String>>
result,ArrayList<String> list,String s){
if(s.length()==0){
result.add(copyArrayList(list));
int k=list.size();
list.remove(k-1);
return;
}
for (int i = 1; i <= s.length(); i++) {
//ArrayList<String> tempList=new
ArrayList<>();
String tempStr = s.substring(0, i);
if (isPalindrome(tempStr)) {
list.add(s.substring(0, i));
String str = s.substring(i);
subString(result, list, str);
}
}
int k=list.size();
if(k>0){
list.remove(k-1);
}
}
//判断一个字符串是否为回文
public boolean isPalindrome(String str){
if(str==null){
return false;
}
if(str.length()<=1){
return true;
}
int i=0;
int j=str.length()-1;
while(i<=j){
if(str.charAt(i)!=str.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
//复制list集合
public ArrayList<String>
copyArrayList(ArrayList<String> list){
ArrayList<String> temp=new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
temp.add(list.get(i));
}
return temp;
}
}
发表于 2017-05-24 18:18:20
回复(0)
大多数人都用递归，用动态规划方法做了下
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public ArrayList < ArrayList<String> > partition(String s) {
ArrayList < ArrayList<String> > result = new ArrayList<>();
ArrayList<String> nullAL = new ArrayList<>();
result.add(nullAL);
int strLength = s.length();
// 遍历s中每个字符
for (int i = 0; i < strLength; i++) {
String palindrome = String.valueOf(s.charAt(i));
ArrayList < ArrayList<String> > additionResult = new ArrayList<>();
for (ArrayList<String> resultAL : result) {
int resultALSize = resultAL.size();
// 如果能和最后一个字符串相等，那么该字符串与最后一个字符串可以构成回文，新建一个list，存储这种情况。
if (resultALSize > 0 && resultAL.get(resultALSize-1).equals(palindrome)) {
ArrayList<String> additionAL = new ArrayList<>(resultAL);
additionAL.set(resultALSize-1, additionAL.get(resultALSize-1)+palindrome);
additionResult.add(additionAL);
}
// 如果能和倒数第二个字符串相等，那么倒数两个字符串与该字符可以构成回文，新建一个list，存储这种情况
if (resultALSize > 1 && resultAL.get(resultALSize-2).equals(palindrome)) {
ArrayList<String> additionAL = new ArrayList<>(resultAL.subList(0, resultALSize-2));
additionAL.add(palindrome+resultAL.get(resultALSize-1)+palindrome);
additionResult.add(additionAL);
}
// 这个字母一定为回文，记录这种情况
resultAL.add(palindrome);
}
result.addAll(additionResult);
}
// 这题坑爹，最后的结果要按每个list中字符串的字典序排列，排列不对不给过
Collections.sort(result, new Comparator<ArrayList < String > >() {
@Override
public int compare(ArrayList<String> o1, ArrayList<String> o2) {
int o1Size = o1.size();
int o2Size = o2.size();
int count = o1Size < o2Size ? o1Size : o2Size;
for (int i = 0; i < count; i++) {
if (o1.get(i).compareTo(o2.get(i)) != 0) {
return o1.get(i).compareTo(o2.get(i));
}
}
return Integer.compare(o1Size, o2Size);
}
});
return result;
}
}
编辑于 2017-05-12 16:34:57
回复(3)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<String>>
partition(String s) {
ArrayList<ArrayList<String>> result=new
ArrayList<ArrayList<String>>();
ArrayList<String> r=new ArrayList<String>();
int length=s.length();
int[][] dp=new int[length][length];
for(int i=0;i<length;i++){
for(int j=i;j<length;j++){
dp[i][j]=1;
int m=i,n=j;
while(m<n){
if(s.charAt(m)!=s.charAt(n)){
dp[i][j]=0;
break;
}
m++;
n--;
}
}
}
dfs(0,s,dp,r,result);
return result;
}
void dfs(int i,String s,int[][] dp,ArrayList<String>
r,ArrayList<ArrayList<String>> result){
if(i==s.length()){
result.add(r);
return;
}
for(int j=i;j<s.length();j++){
if(dp[i][j]==1){
ArrayList<String> tempList=new
ArrayList<String>();
tempList.addAll(r);
tempList.add(s.substring(i,j+1));
dfs(j+1,s,dp,tempList,result);
}
}
}
}
发表于 2017-04-13 14:45:30
回复(0)
public class Solution {
List<List<String>> resultLst;
ArrayList<String> currLst; public List<List<String>> partition(String s) {
resultLst = new ArrayList<List<String>>();
currLst = new ArrayList<String>();
backTrack(s,0); return resultLst;
} public void backTrack(String s, int l){ if(currLst.size()>0 //the initial str could be palindrome && l>=s.length()){
List<String> r = (ArrayList<String>) currLst.clone();
resultLst.add(r);
} for(int i=l;i<s.length();i++){ if(isPalindrome(s,l,i)){ if(l==i)
currLst.add(Character.toString(s.charAt(i))); else currLst.add(s.substring(l,i+1));
backTrack(s,i+1);
currLst.remove(currLst.size()-1);
}
}
} public boolean isPalindrome(String str, int l, int r){ if(l==r) return true; while(l<r){ if(str.charAt(l)!=str.charAt(r)) return false;
l++;r--;
} return true;
}
}
发表于 2017-03-11 19:41:55
回复(0)
问题信息
难度：
15条回答
252收藏
34291浏览
通过挑战的用户
查看代码-
2023-03-12 19:02:38
-
2022-09-12 21:32:49 -
2022-09-12 12:12:30 -
2022-09-08 23:14:00 -
2022-09-06 15:36:35
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
