lintcode-136-分割回文串
2024-10-21 23:10:32
136-分割回文串
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的回文串分割方案。样例
给出 s = "aab"，返回
[
["aa", "b"],
["a", "a", "b"]
]标签
回溯法 深度优先搜索
思路
使用回溯和递归
code
class Solution {
public:
/**
* @param s: A string
* @return: A list of lists of string
*/
vector<vector<string>> partition(string s) {
// write your code here
int size = s.size();
if(size <= 0) {
return vector<vector<string> >();
}
vector<vector<string> > result;
vector<string> temp;
partition(s, 0, temp, result);
return result;
}
void partition(string s, int current, vector<string> &temp, vector<vector<string> > &result) {
if(current == s.size()){
result.push_back(temp);
return;
}
for(int i=current; i<s.size(); i++) {
if(isPalindrome(s, current, i)) {
temp.push_back(s.substr(current,i-current+1));
partition(s, i+1, temp, result);
temp.pop_back();
}
}
}
bool isPalindrome(string s, int begin, int end) {
for(int i=begin, j=end; i<j; i++, j--) {
if(s[i] != s[j]) {
return false;
}
}
return true;
}
};
最新文章
- 推荐一个不错的在线制图网站---ProcessOn
- UITabBarButton 点击失效问题
- Largest BST Subtree
- phpstorm8.0汉化版下载
- org.springframework.web.servlet.PageNotFound No mapping found for HTTP request with URI [/AssetRepair/assetRepairController/test.do] in DispatcherServlet with name 'assetrepair'
- python中的类型转换
- jsp的useBean标签使用
- Mongo散记--聚合（aggregation）&amp; 查询（Query）
- Druid的简介
- Jmeter跨线程组传递参数
- 关于游览器 cookie的操作类
- QString 的用法
- python-布尔值的加法运算
- 【cs229-Lecture3】为什么要选择“最小二乘法”这个指标
- python中文件变化监控-watchdog
- 调整swap分区大小-Linux下安装Oracle时报swap不够解决方法
- spring-security权限控制详解
- eclipse 按装lombok与注解说明
- PokeCats开发者日志（八）
- JS replace()方法替换变量（可以对变量进行全文替换）