您的位置:首页 > 新闻 > 热点要闻 > qq官方网站登录_网站关键词seo费用_精准营销_百度软件应用中心下载

qq官方网站登录_网站关键词seo费用_精准营销_百度软件应用中心下载

2024/12/5 21:26:56 来源:https://blog.csdn.net/Ct314/article/details/143633740  浏览:    关键词:qq官方网站登录_网站关键词seo费用_精准营销_百度软件应用中心下载
qq官方网站登录_网站关键词seo费用_精准营销_百度软件应用中心下载

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

DFS:

class Solution {vector<string> path;vector<vector<string>> v;
public:vector<vector<string>> partition(string s) {dfs(s, 0);return v;}void dfs(string s, int i){  //i 是一个索引,表示当前递归调用时正在考虑的子串的起始位置if (i == s.size()) { //当 i 达到字符串 s 的末尾时,说明找到了一个完整的回文分割方案v.push_back(path);return;}for(int j = i; j < s.size(); j++){if(is(s, i, j)){   // 如果 s[i:j] 是回文path.push_back(s.substr(i, j - i + 1));  // 加入当前子串到 pathdfs(s, j + 1);   // 递归调用,从下一个索引开始继续分割path.pop_back();  // 回溯,撤销前面的选择}}}bool is(string& s, int left, int right){ //检查字符串 s 的 [left, right] 区间是否是回文。while(left < right){if(s[left++] != s[right--]){return false;}}return true;}
};

vector<string> path:用于存储当前分割方案中的回文子串

vector<vector<string>> v:存储所有符合条件的回文分割方案

dfs 函数在每次递归时,从位置 i 开始,检查从 ij 的每个子串是否是回文。一旦找到一个回文子串,就递归到下一个位置(即从 j + 1 开始),继续对剩余的字符串进行分割,直到整个字符串都被分割成回文子串为止。

path.push_back(s.substr(i, j - i + 1));

这一行代码的作用是将字符串 s 的一个子串添加到 path 中。

substr(i, len):用于提取从 i 开始,长度为 len 的子串。

  • i:子串的起始位置(从 0 开始)。
  • len:子串的长度。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com