Zha*_*nan 4 c++ algorithm big-o dynamic-programming palindrome
回文分区
给定一个字符串 s，分区 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();
}
}
}
};
sca*_*age 10
应该是 O(n*2^n)。您基本上是在尝试所有可能的分区。对于长度为 n 的字符串，您将有 2^(n - 1) 种方式对其进行分区。这是因为，一个分区就相当于放了一个“|” 在 b/t 两个字符。有 n - 1 个这样的插槽来放置“|”。每个插槽只有两个选择 - 放置一个“|” 或不放置“|”。因此有 2^(n - 1) 种放置“|”的方法。
然后对于每个唯一的分区，您必须遍历整个字符串（在最坏的情况下，当您有重复字符时）以确保每个分区都是回文。所以 n * 2 ^ (n - 1) = O(n*2^n)。
最坏情况下的运行时间为 O(n * 2^n)。这当然如您所怀疑的那样是指数级的，但没有 O(n^n) 那么糟糕。
以下是我获得 O(n * 2^n) 的方法：您的顶级函数有一个 O(n^2) 循环来初始化备忘录，然后调用整个字符串的 helper 。因此，如果我们将调用等于 n 的助手的成本写为 H(n) (s.length()-start)，那么算法的总成本将是
成本 = H(n) + O(n^2)
H(n) 的基本情况是s.length() - start等于 1 时，然后它只是复制列表的成本：
H(1) = O(n)
对于递归情况，如果if条件memo[start][end]是true每次，将会有 (n-1) 次递归调用，大小为 (n-1), (n-2), (n-3), ..., 2, 1除了这些对 的递归调用之外helper，您还必须substr以相同的大小调用该函数，总共花费 O(n^2)。因此，对于 n>1，H(n) 的总体成本为
H(n) = H(n-1) + H(n-2) + ... + H(1) + O(n^2)
（我会把它写成一个总结，但 SO 没有 LaTeX 支持。）
现在您可以为 H(n-1) 编写相同的表达式，然后代入以简化：
H(n) = 2 H(n-1) + O(n)
这解决了
H(n) = O(n * 2^n)
由于它大于 O(n^2)，因此整个成本也是 O(n * 2^n)。
注意：您可以通过在单个 O(n^3) 循环中预先计算所有子字符串来稍微改进这一点。您也可以对memo数组执行相同的操作。然而，这并没有改变渐进大 O 界。
事实上，O(n * 2^n) 是最佳的，因为在最坏的情况下，字符串是同一字符重复 n 次，例如“aaaaaa”，在这种情况下，有 2^n 个可能的分区，每个分区都有大小n，总输出大小为 Ω(n * 2^n)。