c++ - 这个回文划分算法的时间复杂度是多少？

Question

回文划分

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.

个人认为，时间复杂度为O(n^n)，n为给定字符串的长度。

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();
        }
    }
}
};

Answer 1

应该是 O(n*2^n)。您基本上是在尝试所有可能的分区。对于长度为 n 的字符串，您将有 2^(n - 1) 种方法对其进行分区。这是因为，一个分区相当于放一个“|”在 b/t 中有两个字符。有 n - 1 个这样的槽来放置一个“|”。每个插槽只有两个选择 - 放置一个“|”或不放置“|”。因此有 2^(n - 1) 种放置“|”的方法。

然后对于每个唯一的分区，你必须遍历整个字符串(在最坏的情况下，当你有重复的字符时)以确保每个分区都是回文。所以 n * 2 ^ (n - 1) = O(n*2^n)。