当前位置: 首页 > news >正文

温州今日头条新闻太原百度快照优化排名

温州今日头条新闻,太原百度快照优化排名,政府门户网站建设管理情况,盘锦微信网站建设131. 分割回文串 - 力扣(LeetCode) 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串 示例 1: 输入:s "aa…

131. 分割回文串 - 力扣(LeetCode)

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

>>思路和分析:

  1. 切割问题,有不同的切割方式
  2. 判断回文

代码随想录的Carl老师说:“切割问题类似组合问题”!(这段文字来自代码随想录--分割回文串)

对于字符串abcdef

  • 组合问题选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....
  • 切割问题切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....

>>回溯三部曲:

1).确定回溯函数参数

  • path 存放切割后回文的子串
  • result 保存 path,作为结果集
  • startIndex 来控制for循环的起始位置(表示下一轮递归遍历的起始位置),还用来表示这条切割线.(切割过的地方,不能重复切割,和组合问题也是保持一致的【这句话来自代码随想录】)
vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
void backtracking (const string& s, int startIndex) // startIndex 就用来表示这条切割线

2).递归的终止条件

如果切割线切到了字符串最后面,表示找了一种切割方法,此时终止本层递归!也就是出现这种情况: startIndex >= s.size(),收集结果后直接return;

void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}
}

3).单层搜索的逻辑

>>问题(O_O)?思考:在递归循环中如何截取子串呢?

  • [startIndex,i]:左闭右闭,表示子串的起始位置和终止位置,有截取区间就可以截取子串。substr(startIndex, i - startIndex + 1);

>>问题(O_O)?思考:如何判断所截取子串是否为回文子串呢?

  1. 判断是否为回文子串:isPalindrome(s, startIndex, i),用双指针法
  2. 如果是回文,就加入在vector<string> path中,path 用来记录切割过的回文子串
for (int i = startIndex; i < s.size(); i++) {if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);} else {                // 如果不是则直接跳过continue;}backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back();        // 回溯过程,弹出本次已经添加的子串
}

注意:切割过的位置,不能重复切割,应传入下一层的起始位置为 i + 1,即

  • backtracking(s, i + 1);

 (1)判断是否为回文子串

bool isPalindrome(const string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}
bool isPalindrome(string s) {int left = 0,right = s.size()-1;while(left<=right) {if (s[left] != s[right]) return false;left++;right--;}return true;
}

 (2)C++代码

class Solution {
private:vector<vector<string>> result;vector<string> path; // 放已经回文的子串void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}for (int i = startIndex; i < s.size(); i++) {if (isPalindrome(s, startIndex, i)) {   // 是回文子串// 获取[startIndex,i]在s中的子串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);} else {                                // 不是回文,跳过continue;}backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back(); // 回溯过程,弹出本次已经添加的子串}}bool isPalindrome(const string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}
public:vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n^2)
class Solution {
public:vector<vector<string>> result;vector<string> path; // 放已经回文的子串bool isPalindrome(string s) {int left = 0,right = s.size()-1;while(left<=right) {if (s[left] != s[right]) return false;left++;right--;}return true;}void backtracking(string s,int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if(startIndex >= s.size()) {result.push_back(path);return;}for(int i=startIndex;i<s.size();i++) {// 获取[startIndex,i]在s中的子串string subStr = s.substr(startIndex,i-startIndex+1);if(isPalindrome(subStr)) path.push_back(subStr);// 是回文子串else continue;// 不是回文,跳过backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back(); // 回溯过程,弹出本次已经添加的子串}}vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};

 参考和推荐文章、视频:
带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1c54y1e7k6/?p=67&spm_id_from=pageDriver代码随想录 (programmercarl.com)icon-default.png?t=N7T8https://www.programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E4%BC%98%E5%8C%96

http://www.dinnco.com/news/32444.html

相关文章:

  • vue 做网站seo关键词挖掘工具
  • 做公司网站教程视频中国网络营销网
  • 北京人力资源网站seo关键词推广价格
  • 自己做的网站某个网页打开很慢软件工程培训机构哪家好
  • 高端网站设计找哪个公司百度指数峰值查询
  • 自己怎么做网站啊灰色关键词排名技术
  • 网站建设为什么这么贵seo智能优化系统
  • 中企动力网站推广移动端优化
  • 三门峡网站制作上海app网络推广公司
  • 网站建设客户需求表厨师培训
  • 做高大上分析的网站百度sem运营
  • 网站的按钮怎么做杭州做百度推广的公司
  • 大型网站技术架构核心原理与案例分析站长seo软件
  • 深圳鼎诚网站建设国外黄冈网站推广软件
  • 外贸独立网站制作营销型网站更受用户欢迎的原因是
  • 开发一个简单的系统杭州网站推广与优化
  • 自定义功能的网站今日新闻热点大事件
  • 做微整去那个网站找好的医院百度电脑版下载安装
  • 输入网站查看空间浙江网络科技有限公司
  • 网站建设存在的问题有哪些多少关键词排名优化软件
  • 刚做的网站怎么在百度搜到谷歌网站网址
  • 网页开发和app开发哪个难windows11优化大师
  • 服装工厂做网站的好处榆林百度seo
  • 深圳微信网站建设北京百度快速排名
  • 给别人做设计的网站百度经验怎么赚钱
  • b2c行业网站系统企业网站优化关键词
  • 商标可以做网站吗沈阳seo排名收费
  • 胶州网站设计公司网页制作软件推荐
  • 个人注册的网站可以做公司宣传用吗seo网络营销技术
  • 企业做网站的发票怎样入账福建搜索引擎优化