优化设计电子版_较好的网站建设公司_下载安装百度一下_百度官方网页

题意

把一个字符串分割成多个回文字符串的partition，返回所有的可能partion

链接

https://leetcode.com/problems/palindrome-partitioning/description/

思考

这只是dfs套了一个回文问题

题解

dfs每次截取一段字符串，判断是否是回文
退出条件是遍历到末尾了
dfs传入起始位置u， 从第u位开始截取字符串，一直到末尾，末尾有个指针i。一旦发现是回文了就可以继续截取回文。下一个dfs是从第i+1开始

class Solution {
public:vector<vector<string>> res;vector<vector<string>> partition(string s) {vector<string> tmp;dfs(0, s, tmp);return res;}void dfs(int u, string s, vector<string>& tmp) {if( u == s.size()) {res.push_back(tmp);}for(int i = u; i < s.size(); i++) {if(isPalidrome(s, u, i)) {string tmpStr = s.substr(u, i-u+1);tmp.push_back(tmpStr);dfs(i+1, s, tmp);tmp.pop_back();}}}bool isPalidrome(string s, int u, int i) {int l = u;int r = i;while(l < r) {if(s[l] == s[r]) {l++;r--;} else {return false;}}return true;}
};

时间复杂度$O(n\ast 指数级别)$
空间复杂度$O(n)$