回文分割
给定一个字符串s，将s分割成若干个回文子串。
返回所有可能的回文分割结果。
个人认为时间复杂度为O(n^n)，其中n是给定字符串的长度。
感谢Dan Roche，紧密时间复杂度= O(n* (2^n))，具体细节请参见下文。
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> list;
vector<string> subList;
// Input validation.
if (s.length() <= 1) {
subList.push_back(s);
list.push_back(subList);
return list;
}
int len = s.length();
vector<vector<bool>> memo(len, vector<bool>(len));
for (int i = 0; i < len; i ++) {
for (int j = 0; j < len; j ++) {
if (i >= j) memo[i][j] = true;
else memo[i][j] = false;
}
}
int start = 0;
helper(s, start, list, subList, memo);
return list;
}
void helper(string s, int start,
vector<vector<string>> &list, vector<string> &subList,
vector<vector<bool>> &memo) {
// Base case.
if (start > s.length() - 1) {
vector<string> one_rest(subList);
list.push_back(one_rest);
return;
}
for (int len = 1; start + len <= s.length(); len ++) {
int end = start + len - 1;
memo[start][end] = (len == 1) ||
(memo[start + 1][end - 1] && s[start] == s[end]);
if (memo[start][end] == true) {
// Have a try.
subList.push_back(s.substr(start, len));
// Do recursion.
helper(s, end + 1, list, subList, memo);
// Roll back.
subList.pop_back();
}
}
}
};
partition函数中的算法看起来像是O(n^2)，但我不确定你的helper函数是什么，因为它是递归的，我还没有在脑海中模拟它。 - Dai