重庆网站建设网站,灰色推广,河南省南阳市建设局网站,局域网的常用技术是什么给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1#xff1a;
输入#xff1a;s aab 输出#xff1a;[[a,a请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1
输入s aab 输出[[a,a,b],[aa,b]]
示例 2
输入s a 输出[[a]]
提示
1 s.length 16s 仅由小写英文字母组成 AC:
/** lc appleetcode.cn id131 langcpp** [131] 分割回文串*/// lc codestart
class Solution {
private:vectorstring path;vectorvectorstring result;bool isPalidrome(string s, int start, int end) {for(int i start, j end; i j; i, j--){if(s[i] ! s[j])return 0;}return 1;}void backtracking(string s, int startIndex) {if(startIndex s.size()){result.push_back(path);return ;}for(int i startIndex; i s.size(); i) {if(isPalidrome(s, startIndex, i)) {string str s.substr(startIndex, i - startIndex 1);path.push_back(str);backtracking(s, i 1);path.pop_back();}}return ;}
public:vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};
// lc codeend第一次提交的时候出现了没使用引用类型但是通过了 有没有大佬帮忙解释下不使用浪费的空间资源以及其底层逻辑
/** lc appleetcode.cn id131 langcpp** [131] 分割回文串*/// lc codestart
class Solution {
private:vectorstring path;vectorvectorstring result;bool isPalidrome(string s, int start, int end) {for(int i start, j end; i j; i, j--){if(s[i] ! s[j])return 0;}return 1;}void backtracking(string s, int startIndex) {if(startIndex s.size()){result.push_back(path);return ;}for(int i startIndex; i s.size(); i) {if(isPalidrome(s, startIndex, i)) {string str s.substr(startIndex, i - startIndex 1);path.push_back(str);backtracking(s, i 1);path.pop_back();}}return ;}
public:vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};
// lc codeend另外附上最接近一段时间学习回溯算法的总结
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}------------ 诸君共勉 ---------------
