What's the time complexity of this algorithm for Palindrome Partitioning?
algorithm, big-o, c++, dynamic-programming, palindrome
Solution
The worst-case running time is O(n * 2^n). This is of course exponential as you suspected, but not as bad as O(n^n).
Here's how I got O(n * 2^n): Your top-level function has an O(n^2) loop to initialize memo, and then a call to helper on the entire string. So if we write H(n) for the cost of calling helper with `(s.length()-start)` equal to n, then the total cost of your algorithm will be
cost = H(n) + O(n^2)
The base case for H(n) is when `s.length() - start` equals 1, and then it's just the cost of copying the list:
H(1) = O(n)
And for the recursive case, if the `if` condition `memo[start][end]` is `true` every time, there will be (n-1) recursive calls on size (n-1), (n-2), (n-3), ..., 2, 1. In addition to these recursive calls to `helper`, you also have to call the `substr` function on the same sizes, which costs O(n^2) in total. So overall the cost of H(n), for n>1, is
H(n) = H(n-1) + H(n-2) + ... + H(1) + O(n^2)
(I would write that as a summation but SO doesn't have LaTeX support.)
Now you can write the same expression for H(n-1), then substitute back to simplify:
H(n) = 2 H(n-1) + O(n)
And this solves to
H(n) = O(n * 2^n)
Since that is larger than O(n^2), the whole cost is also O(n * 2^n).
Note: You could slightly improve this by pre-computing all the substrings up front, in a single O(n^3) loop. You might as well do the same for the `memo` array. However, this doesn't change the asymptotic big-O bound.
In fact, O(n * 2^n) is optimal, because in the worst case the string is a repetition of the same character n times, like "aaaaaa", in which case there are 2^n possible partitions, each having size n, for a total output size of Ω(n * 2^n).
Problem
Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Personally I think, the time complexity is O(n^n), n is the length of the given string. Thank you Dan Roche, the tight time complexity = O(n* (2^n)), check details below. ``` #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(); } } } }; ```