(回溯) LeetCode 131. 分割回文串

原题链接

一. 题目描述

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

示例 1：

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

示例 2：

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

提示：

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

二. 解题思路

首先得明确什么是回文串，回文串就是能够对称的字符串，还是老样子。

1. 明确递归参数：字符串s 和当前路径的起点 startindex 。

2. 确定递归的终止条件：当startindex 的大小超过字符串的长度的时候终止，证明已经切割到了字符串的最后，直接将path 路径添加到结果数组res 中即可，这里小伙伴可能要问了，你这还没有判断是不是回文串，对，因为我在后面的单层递归中做了限制，只有回文子串才能进path 数组。所以这里的path 数组中一定是回文子串。

3. 单层递归逻辑：相信做了这么多的题目了，一定知道怎么写吧，只需要加一条判断是不是回文子串的限制条件即可，如果是将其加入到path 数组中进行递归即可，如果不是直接continue；最后做好回溯即可。

话不多说！！！上代码！！

三. 代码

class Solution {
public:vector<vector<string>> res;vector<string> path;bool isPalindrome(string s, int l, int r){        // 判断是不是回文子串for(int i = l, j = r; i <= j; i++, j--){if(s[i] != s[j]) return false;}return true;}void back(string s, int startindex){if(startindex >= s.size()){res.push_back(path);return;}for(int i = startindex; i < s.size(); i++){if(isPalindrome(s, startindex, i)){string str = s.substr(startindex, i - startindex + 1);path.push_back(str);back(s, i + 1);path.pop_back();    // 回溯}}}vector<vector<string>> partition(string s) {back(s, 0);return res;}
};

四. 总结

如果你将前面的题目做了练习的话相信这类题目已经非常简单了吧！！！继续加油！！！

时间复杂度：O(n * 2^n)

空间复杂度：O(n^2)

喜欢的话给个关注吧！！