LeetCode131 分割回文串

前言

题目： 131. 分割回文串
文档： 代码随想录——分割回文串
编程语言： C++
解题状态： 没搞出来

思路

其实切割问题类似组合问题，但是依旧很困难，知道如何去切割也是一个难点。

代码

class Solution {
private:vector<vector<string>> result;vector<string> path;void backtracking(const string& s, int startIndex) {if (startIndex >= s.size()) {result.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);} else {continue;}backtracking(s, i + 1);path.pop_back();}}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;}public:vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};

• 时间复杂度： $O(n\ast 2^n)$
• 空间复杂度： $O(n^2)$