本文主要是介绍Leetcode 131.分割回文串 回溯 C++实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Leetcode 131. 分割回文串
问题:给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
算法:
创建二维返回数组 ans ,和临时数组 path 。
进入 dfs 函数,当 i==n 时,证明已经递归到最后一个元素,执行完就可以 return 。从 i 到末尾,如果是回文就加入到 path 数组中,然后进入下一层递归。递归结束后将 path 存入返回数组 ans 中,最后恢复现场准备进入下一次递归。
代码:
class Solution {// 判断是否是回文字符串bool isPalindrome(string& s,int left,int right){while(left < right)if(s[left++] != s[right--]) return false;return true;}
public:vector<vector<string>> partition(string s) {vector<vector<string>> ans;// 返回数组ansvector<string> path;// 临时数组pathint n = s.length();// 字符串s的长度nauto dfs = [&](auto&& dfs,int i){if(i == n){// 结束ans.emplace_back(path);return ;}for(int j = i;j < n;j++){if(isPalindrome(s,i,j)){path.push_back(s.substr(i,j - i + 1));dfs(dfs,j + 1);// 进入下一层递归path.pop_back();// 恢复现场}// 如果不满足回文条件,不能return,要继续向后加字母。例如efe这个字符串,ef 不满足条件,但是向后加字母到 efe 就又满足了}};dfs(dfs,0);// 递归入口return ans;}
};
p.s. string.substr( a , b ) : 从 string 的第 a 个位置开始,连续读取 b 个数量的字符。
这篇关于Leetcode 131.分割回文串 回溯 C++实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!