Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
思路：
回溯，但是不是常规回溯，因为解向量大小不定，需要动态判断。 下面是我写的代码， 只用了19ms 非常快， 自己挺满意的。
感受：之前做过DP求最少切几刀令所有部分都是回文，跟这个有点像。 觉得凡是求最的都是用DP，凡是求所有解的都是用回溯。
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
if(s.empty())
return ans;
vector<vector<bool>> isPalindrome(s.length(), vector<bool>(s.length(), false));
vector<vector<int>> S(s.length(), vector<int>(, )); //每个深度候选范围 用下标范围来记录
int k = ;
vector<string> X;
while(k >= )
{
while(k >= && S[k][] < s.length()) //当前深度判断完毕 通过当前范围结束下标到达s的最后
{
int i = S[k][]; //当前深度判断位置的起始下标
int j = S[k][]; //当前深度判断位置的结束下标
if(s[i] == s[j] && (j - i < || isPalindrome[i+][j - ])) //分次判断是否为回文，每次使用历史信息
{
isPalindrome[i][j] = true;
while(X.size() >= k + ) //X长度不固定，所以用的时候会有上一次求解的值，我们需要把多出的部分弹出 ！！特别注意
{
X.pop_back();
}
X.push_back(s.substr(i, j - i + ));
S[k][]++;
if(S[k][] < s.length())
{
k++;
S[k][] = S[k - ][];
S[k][] = S[k - ][];
}
else
{
ans.push_back(X);
}
}
else
{
S[k][]++;
}
}
k--;
}
return ans;
}
};
随机推荐
-
C fread
fread是一个函数.从一个文件流中读数据,最多读取count个元素,每个元素size字节,如果调用成功返回实际读取到的元素个数,如果不成功返回 0. 函数原型 size_t fread ( void ...
-
MSIL 教程（二）：数组、分支、循环、使用不安全代码和如何调用Win32 API（转）
转自:http://www.cnblogs.com/Yahong111/archive/2007/08/16/857574.html 续上文[翻译]MSIL 教程(一) ,本文继续讲解数组.分支.循环 ...
-
MySQL Server 5.7解压版缺少文件无法启动
如题: 一般认为5.7中mysql目录下 缺少data/mysql/目录,导致无法启动: 解决方案: 重新安装5.6即可: 1.删除5.7中安装的服务: 到mysql\bin目录下运行:mysqld ...
-
关于 xcode 工程编译报错 undefined symbol _res_9_init的解决办法
将libresolv.dylib 添加到工程引用中(通过build phases中).补充: _res_9_init定义在resolv.h中,可以参考http://www.opensource. ...
-
【转】Cygwin访问Windows驱动器
From:http://www.cygwin.cn/site/info/show.php?IID=1000 由于自己的项目需要使用Linux内核,所以自己在windows下安装了一个Linux虚拟机! ...
-
ASP.net中导出Excel的简单方法介绍
下面介绍一种ASP.net中导出Excel的简单方法 先上代码:前台代码如下(这是自己项目里面写的一点代码先贴出来吧) <div id="export" runat=&quo ...
-
20151210--MVC
package com.hanqi; import java.io.IOException; import java.sql.*; import java.text.SimpleDateFormat; ...
-
利用OpenCV和MFC对话框建设一个有滑动条控制的播放器--转
(一)问题的提出: OpenCV有一个很简单的播放视频文件并加载滑动条的程序,但是如何用MFC对话框来创建一个有滑动条控制的播放器呢,网络上四处搜索都没有代码可以参考,下的都是些骗子链接文件,很过分, ...
-
Zookeeper Client简介
直接使用zk的api实现业务功能比较繁琐.因为要处理session loss,session expire等异常,在发生这些异常后进行重连.又因为ZK的watcher是一次性的,如果要基于wather ...
-
Linux设备驱动程序 第三版 读书笔记（一）
Linux设备驱动程序 第三版 读书笔记(一) Bob Zhang 2017.08.25 编写基本的Hello World模块 #include <linux/init.h> #inclu ...