建自己的网站多少钱,个人做网站怎么赚钱,烟台cms建站模板,微信小程序商城怎么开发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();}}}
};
