制作一个网站怎么做的,个人介绍网页,网站建设需要什么人才,建筑英才网最新招聘LeetCode-131 分割回文串 题目描述解题思路C 代码 题目描述
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1#xff1a;
输入#xff1a;s “aab” 输出#xff1a;[[“a”,“a”,“b”],… LeetCode-131 分割回文串 题目描述解题思路C 代码 题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1
输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2
输入s “a” 输出[[“a”]]
解题思路
B站题目讲解 在解决组合、排列、子集、切割问题时我们选择使用回溯算法。
用指针 start 试着去切切出一个回文串基于新的 start继续往下切直到 start 越界 每次基于当前的 start可以选择不同的 i切出 start 到 i 的子串我们枚举出这些选项 i
切出的子串满足回文将它加入部分解 path 数组并继续往下切递归切出的子串不是回文跳过该选择不落入递归继续下一轮迭代
C 代码
class Solution {
public:vectorvectorstring partition(string s) {back_tracking(s, 0);return res;}
private:vectorvectorstring res;vectorstring path;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;}void back_tracking(string s, int index) {if (index s.size()) {res.push_back(path);return;} else {for (int i index; i s.size(); i) {if (isPalindrome(s, index, i)) {path.push_back(s.substr(index, i - index 1));} else {continue;}back_tracking(s, i 1);path.pop_back();}}}
};
