删除无效括号-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

我知道这是一个有点老的问题，但我只想指出，在我所知道的每个实现中，字符串构建都是O(n)，并且有O(2^n)个叶子，如上所述。所以O(n*2^n)是正确的时间复杂度。