【Hot 100 刷题计划】 LeetCode 131. 分割回文串 | C++ 回溯算法基础切割法

张开发
• 2026/4/14 15:56:42 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【Hot 100 刷题计划】 LeetCode 131. 分割回文串 | C++ 回溯算法基础切割法
LeetCode 131. 分割回文串 题目描述题目级别中等给你一个字符串s请你将s分割成一些子串使每个子串都是回文串。返回s所有可能的分割方案。示例 1:输入s aab输出[[a,a,b],[aa,b]]示例 2:输入s a输出[[a]] 破题思路DFS 模拟切割线这道题是典型的组合/分割问题非常适合使用回溯算法DFS。我们可以把字符串想象成一条长长的蛋糕我们要决定在哪里“下刀”。递归参数u代表我们当前准备切蛋糕的起始位置。横向遍历i代表我们这一刀切在哪。子串s[u...i]就是我们切下来的这一块。合法性检验与纵向递归如果我们切下来的这一块是回文串我们就把它装进当前的路径篮子path里然后拿着剩下部分的起始位置i 1继续向深处递归。回溯当这一条路探索完退回来时我们需要把刚刚装进篮子的那一块拿出来path.pop_back()去尝试其他的切法。(⚠️ 细节提醒在 C 中传递字符串时务必使用const string s避免每一次递归都发生大规模的内存拷贝这是大厂面试的红线) C 代码实现 (基础双指针判断)classSolution{public:vectorvectorstringres;vectorstringpath;vectorvectorstringpartition(string s){dfs(s,0);returnres;}// 优化点使用 const string 避免大量字符串拷贝耗时voiddfs(conststrings,intu){// 终止条件切割线已经到达了字符串的末尾说明找到了一种完全切分方案if(us.size()){res.push_back(path);return;}// i 代表这一刀切下去的位置切出的子串为 s[u...i]for(intiu;is.size();i){// 如果切出来的这一块是回文串才允许继续往下切if(isPart(s,u,i)){path.push_back(s.substr(u,i-u1));// 处理节点将回文子串加入路径dfs(s,i1);// 向下递归从下一截开始继续切path.pop_back();// 回溯撤销选择尝试下一刀切得更长一点}}}// 双指针法判断 s[l...r] 是否为回文串boolisPart(conststrings,intl,intr){while(lr){if(s[l]!s[r--])returnfalse;}returntrue;}};

更多文章