algorithm - 删除无效括号 - Leetcode 时间复杂度

Question

我在leetcode上解决这个问题，问题陈述如下。

为了使输入字符串有效，删除最少数量的无效括号。返回所有可能的结果。

注意:输入的字符串可能包含括号(和)以外的字母。

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

一段时间后，我能够解决问题。但是我无法找到我的解决方案的时间复杂度。我的代码如下。请帮我找出时间复杂度。

    class Solution {
public:

    void balance(string s, int curr_index, int changes, int max_changes, unordered_set<string> &memo, vector<string> &result){

        if(memo.find(s) != memo.end()){
            return;
        }

        if(changes == max_changes){
            int opening = 0;
            for(int i = 0; i < s.length(); i++){
                if(s[i] == '('){
                    opening++;
                }
                else if(s[i] == ')'){
                    if(opening == 0){
                        return;
                    }
                    else{
                        opening--;
                    }
                }
            }
            if(opening == 0){
                result.push_back(s);
            }
        }
        else if(changes > max_changes || curr_index >= s.length()){
            return;
        }
        else{
            if(s[curr_index] == '(' || s[curr_index] == ')'){
                string temp = s;
                temp.erase(temp.begin() + curr_index);
                balance(temp, curr_index, changes + 1, max_changes, memo, result);
            }

            balance(s, curr_index + 1, changes, max_changes, memo, result);
        }

        memo.insert(s);

    }


    vector<string> removeInvalidParentheses(string s) {

        int opening = 0;
        int min_changes = 0;

        vector<string> result;

        for(int i = 0; i < s.length(); i++){
            if(s[i] == ')' && opening == 0){
                min_changes++;
            }
            else if(s[i] == ')' && opening != 0){
                opening--;
            }
            else if(s[i] == '('){
                opening++;
            }
        }

        min_changes += opening;

        if(min_changes == s.length()){
            result.push_back("");
            return result;
        }
        else{

            unordered_set<string> memo;

            balance(s, 0, 0, min_changes, memo, result);

            return result;
        }

    }
    };

Answer 1

它是指数级的。您无能为力，因为输出大小可能是指数级的。

考虑以下示例:(a(a(a(a.....))))))，其中 (a 对的数量是右括号数量的两倍。很明显，我们需要恰好删除一半的左括号，而且很明显，删除它们的任何子集都会产生一个唯一的字符串。

令字符串的长度为5n。然后我们有 2n '(' and 'a' and n ')'。有2n 种选择n 的方法来删除左括号的子集并得到一个有效的字符串，它是字符串长度的指数。