[Leetcode Week13]Palindrome Partitioning
2024-08-29 18:37:38
Palindrome Partitioning 题解
原创文章，拒绝转载
题目来源：https://leetcode.com/problems/palindrome-partitioning/description/
Description
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"]
]
Solution
class Solution {
public:
vector<vector<string>> partition(string s) {
int len = s.length();
vector<vector<string>> res;
vector<string> path;
dfs(0, s, path, res);
return res;
}
void dfs(int idx, string& str, vector<string>& path, vector<vector<string>>& res) {
if (idx == str.length()) {
res.push_back(path);
return;
}
for (int i = idx; i < str.size(); i++) {
if (isPalindrome(str, idx, i)) {
path.push_back(str.substr(idx, i - idx + 1));
dfs(i + 1, str, path, res);
/* pop back every time in recurse stack,
* than all the paces added in dfs can be remove */
path.pop_back();
}
}
}
bool isPalindrome(string& str, int start, int end) {
while (start < end) {
if (str[start] != str[end]) {
return false;
}
start++;
end--;
}
return true;
}
};
解题描述
这道题是目的是找到一个字符串中所有由回文子串组成的集合，算法是对给出的字符串进行遍历，查找所有回文子串，对每个回文子串再进行DFS查找新的回文子串，这样就能找到所有由回文子串切分的子串的集合。
最新文章
- Oracle 分页
- 设计模式 之 原型模式（ProtoType）
- .net中的序列化
- C/C++代码中的笔误
- .NET 4.0 任务和并行编程系列
- 第一个servlet小例子
- ruby使用IO类读写文件
- 子窗体显示在任务栏，且子窗体中又有弹窗（CreateParams修改三个风格参数）
- 提交服务器 post get
- 取文件的大小 （KB,MB,GB...）
- 字符串操作函数<string.h>相关函数strcpy,strcat,等源码。
- 基于visual Studio2013解决C语言竞赛题之1002字符打印
- LCA——求解最近公共祖先
- UITabbar的一些常规用法(总结）
- 初识KNN
- docker+openvswitch实现主机与容器的网络通信
- 双向链表--首页大小不一卡片排序 --- react --- js
- js教程
- Java 内存溢出思维导图
- In file included from adlist.c:34:0: zmalloc.h:50:31: 致命错误：jemalloc/jemalloc.h：没有那个文件或目录