给定一个字符串s，分割s使得s的每一个子串都是回文串
返回所有的回文分割结果。（注意：返回结果的顺序需要和输入字符串中的字母顺序一致。）
[编程题]分割回文串
使用回溯法求解，不是最优但是比较好理解
动态规划的解法下次更新
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
if (s == null || s.length() == 0)
return res;
solve(s, 0, new ArrayList<String>(), res);
return res;
}
private void solve(String s, int index, ArrayList<String> preList, ArrayList<ArrayList<String>> res) {
if (index == s.length()) {
res.add(new ArrayList<String>(preList));
return;
}
ArrayList<String> list = new ArrayList<String>(preList);
for (int i = index + 1; i <= s.length(); i++) {
if (isPalindrom(s.substring(index, i))) {
list.add(s.substring(index, i));
solve(s, i, list, res);
list.remove(list.size() - 1);
}
}
}
private boolean isPalindrom(String s) {
if (s == null)
return false;
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l++) != s.charAt(r--))
return false;
}
return true;
}
}
发表于 2018-06-05 16:25:20
回复(3)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
ArrayList<String> list = new ArrayList<String>();
if (s == null || s.length() == 0)
return result;
calResult(result,list,s);
return result;
}
/**
* 判断一个字符串是否是回文字符串
*/
private boolean isPalindrome(String str){
int i = 0;
int j = str.length() - 1;
while (i < j){
if (str.charAt(i) != str.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
/**
* 回溯
* @param result : 最终要的结果集 ArrayList<ArrayList<String>>
* @param list : 当前已经加入的集合 ArrayList<String>
* @param str : 当前要处理的字符串
*/
private void calResult(ArrayList<ArrayList<String>> result
, ArrayList<String> list
, String str)
{
//当处理到传入的字符串长度等于0,则这个集合list满足条件，加入到结果集中
if (str.length() == 0)
result.add(new ArrayList<String>(list));
int len = str.length();
//递归调用
//字符串由前往后，先判断str.substring(0, i)是否是回文字符串
//如果是的话，继续调用函数calResult，把str.substring(i)字符串传入做处理
for (int i=1; i<=len; ++i){
String subStr = str.substring(0, i);
if (isPalindrome(subStr)){
list.add(subStr);
String restSubStr = str.substring(i);
calResult(result,list,restSubStr);
list.remove(list.size()-1);
}
}
}
}
发表于 2017-07-25 17:03:26
回复(5)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
int len=s.length();
ArrayList<ArrayList<String>> list=new ArrayList();
if(len<=0){return null;}
if(len==1){
ArrayList<String> templist=new ArrayList();
templist.add(s);
list.add( templist);
}else{
for(int i=1;i<len+1;i++){
String temp=s.substring(0, i);
if(isPalindrome(temp)){
if(i==len){
ArrayList<String> templist=new ArrayList();
templist.add(temp);
list.add( templist);
}else {
List list1=partition(s.substring(i));
for(int j=0;j<list1.size();j++){
ArrayList<String> templist=new ArrayList();
templist.add(temp);
templist.addAll((Collection) list1.get(j));
list.add( templist);
}
}
}
}
}
return list;
}
boolean isPalindrome(String s){
int len=s.length();
boolean flag=false;
if(len==1){
flag=true;
}else{
int index=len/2;
if(len%2==1){
index=len/2+1;
}
if(s.substring(0,len/2).equals(new StringBuffer(s.substring(index)).reverse().toString())){
flag=true;
}
}
return flag;
}
}
发表于 2016-09-11 11:37:19
回复(3)
大多数人都用递归，用动态规划方法做了下
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)
class Solution {
public:
vector<vector<string> > res;
vector<string> temp;
bool isHunwen(string s){
bool flag = true;
int left = 0;
int right = s.size() - 1;
while (left <= right){
if (s[left] != s[right]){
flag = false;
break;
}
left++;
right--;
}
return flag;
}
void dfs(string s, int pos){
if (pos >= s.size()){
res.push_back(temp);
return;
}
for (int i = 1; i <= s.size()-pos; i++){
string sub = s.substr(pos, i);
if (isHunwen(sub)){
temp.push_back(sub);
dfs(s, pos + i);
temp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
dfs(s, 0);
return res;
}
};
发表于 2016-07-24 14:43:33
回复(0)
主要思路是回溯：
leetcode 大神代码，还有配图，我就改成了ArrayList
public class myleetcode_139 { ArrayList<ArrayList<String>> resultList; ArrayList<String> current; public ArrayList<ArrayList<String>> partition(String s) { resultList = new ArrayList<ArrayList<String>>(); current = new ArrayList<String>(); findPalindrome(s, 0); return resultList; } /** * 主要思路是回溯 * @param str * @param left */ private void findPalindrome(String str, int left) { //回溯返回条件，left指针已到最后，也就是回溯到底了 if (current.size() > 0 && left >= str.length()) { ArrayList<String> tempList = (ArrayList<String>) current.clone(); resultList.add(tempList); } for (int right = left; right < str.length(); right++) { //不是回文的话，直接right++； if (isPalindrome(str, left, right)) { //添加回文 if (left == right) { current.add(Character.toString(str.charAt(left))); }else{ current.add(str.substring(left, right +1)); } //进行回溯 findPalindrome(str, right + 1); //移除刚刚添加的元素，也就是回到之前的状态，以便走其他分支 current.remove(current.size() - 1); } } } public boolean isPalindrome(String str, int left, int right) { if (left == right) { return true; } while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; } }
编辑于 2017-07-12 16:35:50
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> res = new ArrayList<>();
help(res,new ArrayList<String>(),s);
return res;
}
private void help(ArrayList<ArrayList<String>> res, ArrayList<String> temp, String s) {
if(s.length() == 0){
res.add(new ArrayList<>(temp));
return;
}
for (int i = 1; i <= s.length(); i++) {
String t = s.substring(0, i);
if(isPalindrome(t)){
temp.add(t);
help(res,temp,s.substring(i));
temp.remove(temp.size()-1);
}
}
}
private boolean isPalindrome(String t) {
return new StringBuilder(t).reverse().toString().equals(t);
}
}
发表于 2017-09-03 20:31:44
回复(2)
用回溯法，递归求解。具体解析看下面代码的注释。
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)
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)
//DFS方法
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string> >res;
if(s.size()<=0) return res;
vector<string>temp;
int len=s.size();
for(int i=1;i<=len;++i)
{
string word=s.substr(0,i);//先看str[0-i)是不是回文串
if(!judge(word)) continue;//如果不是返回i+1
temp.push_back(word);//如果是，递归调用返回后半字符串的所有可能回文串
vector<vector<string> >part=partition(s.substr(i));
Combine(res,temp,part);//合并结果
temp.clear();//清除容器
}
return res;
}
private:
bool judge(string str)//判断是否为回文串
{
if(str.size()<=0) return false;
if(str.size()==1) return true;
else{
int front=0;
int later=str.size()-1;
while(later>front)
{
if(str[front]!=str[later])
return false;
--later;
++front;
}
return true;
}
}
void Combine(vector<vector<string> >&res,vector<string>temp,vector<vector<string> >part)
{
if(part.size()<=0) res.push_back(temp);
vector<string>storage;
for(int i=0;i<part.size();++i)
{
storage=temp;
for(int j=0;j<part[i].size();++j)
storage.push_back(part[i][j]);
res.push_back(storage);
}
return ;
}
};
编辑于 2019-04-30 10:53:33
回复(0)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
if(s.empty())
return result;
vector<string> temp_string;
look_for(s,0,temp_string,result);
return result;
}
private:
bool ispalindrome(string &s){
string temp=s;
reverse(temp.begin(),temp.end());
return s==temp;
}
void look_for(string &s,int pos,vector<string> &temp_string,vector<vector<string>> &result){
if(pos==s.size()){
result.push_back(temp_string);
}
for(int i=1;i<=s.size()-pos;++i){
string temp=s.substr(pos,i);
if(ispalindrome(temp)){
temp_string.push_back(temp);
look_for(s,pos+i,temp_string,result);
temp_string.pop_back();
}
}
}
};
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
if(s.empty())
return result;
vector<string> temp_string;
look_for(s,0,temp_string,result);
return result;
}
private:
bool ispalindrome(string &s){
string temp=s;
reverse(temp.begin(),temp.end());
return s==temp;
}
void look_for(string &s,int pos,vector<string> &temp_string,vector<vector<string>> &result){
if(pos==s.size()){
result.push_back(temp_string);
}
for(int i=1;i<=s.size()-pos;++i){
string temp=s.substr(pos,i);
if(ispalindrome(temp)){
temp_string.push_back(temp);
look_for(s,pos+i,temp_string,result);
temp_string.pop_back();
}
}
}
};
发表于 2018-05-06 10:08:49
回复(0)
import java.util.ArrayList;
public class Solution {
ArrayList<ArrayList<String>> resultList=new ArrayList<ArrayList<String>>();
ArrayList<String> temp=new ArrayList<>();
public ArrayList<ArrayList<String>> partition(String s) {
findPalindrome(s,0);
return resultList;
}
private void findPalindrome(String s,int left){
//size大于0防止将空数组也置入
if(temp.size()>0&&left>=s.length()){
//add方法是放入引用对象所以要先clone对象在放入
ArrayList<String> tempList = (ArrayList<String>) temp.clone();
resultList.add(tempList);
}
for(int right=left;right<s.length();right++){
String stemp=s.substring(left,right+1);
if(isPalindrome(stemp)){
temp.add(stemp);
//回溯的思想
findPalindrome(s,right+1);
//回溯到原来状态要移除上一步走的路径
temp.remove(temp.size()-1);
}
}
}
private boolean isPalindrome(String s){
if(s.length()==1){return true;}
if(s.substring(0,s.length()/2).equals(new StringBuffer(s.substring((s.length()/2+s.length()%2))).reverse().toString()))
{
return true;
}
return false;
}
}
编辑于 2018-03-02 10:59:34
回复(0)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string> >result;
vector<string> temp;
if(s.size()==0) return result;
recur(0,0,s,temp,result);
return result;
}
void recur(int i,int j,string s,vector<string> temp,vector<vector<string>>& result){
if(j+1==s.size() && ispalindrome(i,j,s))//最后一个回文
{ temp.push_back(s.substr(i,j-i+1));
result.push_back(temp);
return ;
}
if(j+1==s.size()) return ;
if(ispalindrome(i,j,s))
{
vector<string> copy=temp;
copy.push_back(s.substr(i,j-i+1));
recur(j+1,j+1,s,copy,result);
}
recur(i,j+1,s,temp,result);
}
bool ispalindrome(int i,int j,string s){
while(i<j)
{
if(s[i]!=s[j]) return false;
else
{
i++;
j--;
}
}
return true;
}
};
发表于 2018-03-01 16:49:21
回复(0)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string> > result; vector<string> v; DFS(s,v,result); return result;
}
void DFS(string s,vector<string> &v,vector<vector<string> > &result){
if(s.size() < 1){
result.push_back(v);
return; } for(int i=0;i<s.size();i++) { int begin = 0; int end = i; while(begin < end) { if(s[begin] == s[end]) { begin++; end--; }else break; } if(begin >= end) { v.push_back(s.substr(0,i+1)); DFS(s.substr(i+1), v, result); v.pop_back(); } } }
};
发表于 2017-09-19 13:56:16
回复(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)
class Solution
{
public:
unordered_map<int, vector<int>> m_huiwen;
unordered_map<int, vector<vector<string>>> m;
bool is_palindrome(int start,int finish)
{
while (start < finish)
{
if (str[start] == str[finish])
{
++start;
--finish;
}
else return false;
}
return true;
}
{
public:
unordered_map<int, vector<int>> m_huiwen;
unordered_map<int, vector<vector<string>>> m;
bool is_palindrome(int start,int finish)
{
while (start < finish)
{
if (str[start] == str[finish])
{
++start;
--finish;
}
else return false;
}
return true;
}
vector<vector<string>> partition(string s)
{
str = s;
for (int i = 0; i < (int)s.length(); ++i)
{
for (int j = i; j >= 0; --j)
{
if (is_palindrome(j, i))
{
m_huiwen[i].push_back(j);
}
}
}
for (int i = 0; i < (int)s.length(); ++i)
{
m[i] = solve(i);
}
return m[s.length() - 1];
}
vector<vector<string>> solve(int finish)
{
vector<vector<string>> ans;
if (finish == 0)
{
ans.push_back(vector < string > {str.substr(0, 1)});
return ans;
}
for (auto c : m_huiwen[finish])
{
string s = str.substr(c, finish - c + 1);
if (c == 0)
{
ans.push_back(vector < string > {s});
}
else
{
vector<vector<string>> vec = m[c - 1];
for (auto& c : vec)
{
c.push_back(s);
ans.push_back(c);
}
}
}
sort(ans.begin(),ans.end());
return ans;
}
string str;
};
发表于 2017-07-18 16:37:26
回复(0)
class Solution {
public:
// backtracking
bool isPalindrome(string &str)
{
int len = str.length();
for(int i=0,j=len-1;i<=j;i++,j--)
if(str[i] != str[j])
return false;
return true;
}
vector<vector<string>> partition(string s)
{
vector<vector<string>> res;
vector<string> combine;
if(s.length() == 0)
return res;
dfs(s,res,combine,0);
return res;
}
void dfs(string &s,vector<vector<string>> &res,vector<string> &combine,int begin)
{
if(begin == s.length())
{
res.push_back(combine);
return;
}
string substring;
for(int i=begin;i<s.length();i++)
{
substring.push_back(s[i]);
if(isPalindrome(substring))
{
combine.push_back(substring);
dfs(s,res,combine,i+1);
combine.pop_back();
}
}
}
};
发表于 2017-07-04 15:19:57
回复(0)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> strPalindrome(NULL);
vector<string> strPath(NULL);
PalindromeDFS(s, strPalindrome, strPath);
return strPalindrome;
}
//递归调用保存
void PalindromeDFS(const string &s, vector<vector<string>> &strPalindrome, vector<string> &strPath)
{
int strLength = s.size();
if (strLength < 1)
{
strPalindrome.push_back(strPath);
return;
}
//判断s从0位置开始字符串大小为1，...，s.size()的子串是否是回文，strPath为所有可能字符串的访问路径，只保存回文到strPalindrome
for (int i = 0; i < strLength; i++)
{
int nBegin = 0;
int nTail = i;
if (IsPalindrome(s.substr(0, i+1)))
{
/*Substring(Int32, Int32):从此实例检索子字符串。 子字符串从指定的字符位置开始且具有指定的长度。*/
strPath.push_back(s.substr(0, i+1));
/*Substring(Int32):从此实例检索子字符串。 子字符串在指定的字符位置开始并一直到该字符串的末尾。*/
PalindromeDFS(s.substr(i + 1), strPalindrome, strPath);
strPath.pop_back();
}
}
}
//判断是不是回文
bool IsPalindrome(const string &s)
{
int nBegin = 0;
int nTail = s.size() - 1;
while (nBegin <= nTail)
{
if (s[nBegin] != s[nTail])
{
return false;
}
nBegin++;
nTail--;
}
return true;
}
};
发表于 2017-04-16 21:52:09
回复(0)
//利用递归的思想
class Solution {
public:
vector<vector<string>> findPal(string s){
int len=s.length();
vector<string> temp;
vector<vector<string>> res1,res2,res;
if(len==1){
temp.push_back(s);
res.push_back(temp);
temp.clear();
return res;
}
res1=findPal(s.substr(1,len-1));
for(int i=0;i<res1.size();i++){
res1[i].push_back(s.substr(0,1));
res.push_back(res1[i]);
}
int pos=s.find(s[0],1);
while(pos!=string::npos){
if(check(s.substr(0,pos+1))){
if(pos==len-1){
temp.push_back(s);
res.push_back(temp);
temp.clear();
break;
}
res2=findPal(s.substr(pos+1,len-pos-1));
for(int i=0;i<res2.size();i++){
res2[i].push_back(s.substr(0,pos+1));
res.push_back(res2[i]);
}
}
pos=s.find(s[0],pos+1);
}
return res;
}
vector<vector<string>> partition(string s) {
vector<vector<string>> res(0);
if(s.length()==0){
return res;
}
res=findPal(s);
for(int i=0;i<res.size();i++){
reverse(res[i].begin(),res[i].end());
}
return res;
}
bool check(string s){
int end =s.length()-1;
for(int i=0;i<end-i;i++){
if(s[i]!=s[end-i])
return false;
}
return true;
}
};
发表于 2017-01-02 16:36:06
回复(0)
//动态规划+递归实现
class Solution {
public:
//返回以s[i]开始的子串的所有拆分情况
vector<vector<string> > dfs(size_t start, vector<vector<bool> >& flag, string s)
{
vector<vector<string> > res;
//到达末尾
if (start == s.length())
{
vector<string> tmp;
res.push_back(tmp);
}
else
{
//分两部分
for (size_t i = start; i < s.length(); i++)
{
//前半部分为回文
if (flag[start][i] == true)
{
//递归计算后半部分
vector<vector<string> > tmp = dfs(i + 1, flag, s);
//将返回的结果插入前半部分，放入res中
for (size_t k = 0; k < tmp.size(); k++)
{
tmp[k].insert(tmp[k].begin(), s.substr(start, i - start + 1));
res.push_back(tmp[k]);
}
}
}
}
return res;
}
vector<vector<string>> partition(string s) {
vector<bool> tmp(s.size(), false);
vector<vector<bool> > flag(s.size(), tmp);
vector<vector<string> > res;
//flag[i][j]为s[i..j]是否为回文串的标志，用动态规划
//flag[i][j] = true (当s[i]==s[j] 且 flag[i+1][j-1]为true)
for (int i = s.size() - 1; i >= 0; i--)
{
for (size_t j = i; j < s.size(); j++)
{
if (i == j)
{
flag[i][j] = true;
}
else
{
if (s[i] == s[j])
{
if (i + 1 == j || flag[i + 1][j - 1] == true)
flag[i][j] = true;
}
}
}
}
//递归找出拆分方法
res = dfs(0, flag, s);
return res;
}
};
发表于 2016-09-17 13:16:16
回复(0)
问题信息
难度：
107条回答
252收藏
34275浏览
通过挑战的用户
查看代码-
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号
